10.1闲话做题纪要10.2闲话做题纪要10.3闲话做题纪要luoguP3241[HNOI2015]开店不难发现两个点在点分树上的\(\operatorname{LCA}\)是一个求距离的好的分割点，考虑点分树。暂且不考虑\([l,r]\)的限制，因为只是一个限制范围的查找。设\(siz_{x}\)表示点分树

点分治点分治适合处理大规模的树上路径信息问题。本质思想是选择一点作为分治中心，将原问题划分为几个相同的子树上的问题，进行递归解决。常见的用于统计树上有关路径的信息。假设当前选定根节点为\(rt\)，则符合条件的路径必然是以下两种之一：经过\(rt\)或一段在\(rt\)上；在

赛时4题，策略重大失误，g题思路假了但是以为是代码问题硬调3.5h，m题本来是可以过的，e是网络流说不定也能过呢。xixike大力平衡树直接打过k题省去思考双优先队列算法的时间，太强A观察到同级同形状括号如果有四个就一定可以交换顺序，而且是充要的，经典括号匹配用栈存储就过了，我代码比较丑

省流：\(45+20+5+0=70\)简称：唐诗在此膜拜\(klz\)\(Heldivis\)\(Sorato\)\(czl\)\(Ech0\_7\)yxanslihe_qwq大佬T1先看的T1，想了一个拓排（其实是看错题了），然后过了第一个样例，然后咋调都过不去，就去码暴力了。过了大概10min发现看错题了，然后一会就想出来个\(O(n^2)\)

前言离A掉一道题最近的一次。过程看完T1以后，想先构一个\(\mathcal{O}(n^3)\)的暴力，但是发现只有10pts，而且算法复杂度接近\(\mathcal{O}(n^4)\)，所以果断放弃。把链的限制写了（然后亏大了），然后开始在CS上面画画。画了一会发现一个简单的dp思路，但是是\(\mathcal{O}(n^

题目传送门前置知识动态树分治|动态开点线段树|标记永久化解法考虑动态点分治。两种操作本质上是将luoguP6329【模板】点分树|震波的操作互换了下，将原需支持单点修改、区间查询的数据结构换成需支持区间修改、单点查询的数据结构即可。区间修改、单点查询的动态开

【20zr提高组十连测day10】心首先不同的操作序列一定在某个时刻使数组内容不同，因此我们只需要统计合法的操作序列数量。一个合法的最终数组形如若干个\(1,M\)，而且\(1,M\)之间可能有若干个\(x\)，长度为\(n+1\)。造成这个数组的操作序列必须满足所有操作\(1,M\)按顺序排列，

显然树上背包。首先一眼会想到的状态：\(dp_{i,j}\)表示\(i\)的子树最后剩下\(j\)个结点的最小代价。然而开始写会发现这并不好DP。于是我们换一个想法：\(dp_{i,j}\)表示\(i\)的子树删去\(j\)个结点的最小代价。则有转移方程：\[dp_{i,j}=\min_{v\inson(i)}\{dp_{i

题解：CF888GXor-MST题目大意：给定\(n\)个点的点权,任意两点间边权是点权的异或和。求这张完全图的MST的权值。思路：Boruvka+Trie树+按位贪心。关键就在于如何求出Boruvka中的best数组。考虑对点权建trie树，对于节点\(i\)本轮的连边，就是找“和它最相似”的那

题目传送门前置知识点分治|树状数组解法维护点对信息，考虑点分治。本题比luoguP4149[IOI2011]Race多了个前缀查询\(\max\)。套个支持单点修改、区间查询\(\max\)的数据结构即可。直接线段树维护区间\(\max\)貌似会TLE，换成树状数组维护前缀\(\max\)即可。注

题目描述有\(n\)座灯塔排成一排，第\(i\)座灯塔的高度是\(a_i\)。你需要求出有多少对\(l<r\)满足\(a_l=a_r\)，且\(\foralll<i<r,a_i<a_l\)。灯塔的高度有\(Q\)次修改，每次给定\(x,h\)，表示将\(a_x\)修改为\(h\)。求出修改之前和每次修改之后的答案。\(n

二叉搜索树众所周知，一个区间可以有许多信息(最大值、\(k\)大值、区间和、区间平方和、区间立方和、区间异或和、区间\(\gcd\)、不同数字个数、颜色段数……)，也有许多修改方式(插入、删除、区间加、区间乘、区间改、区间翻转……)，我们发现其中一些用线段树不是很好维护，这时我们

CF1039DYouAreGivenaTree咋其他题解都带根号？根号是坏文明，这里是俩\(\log\)做法，能够跑到\(300\)ms以内。首先考虑暴力贪心，从叶子向根合并，可以取出一条链的时候就取出来，否则就连一条尽可能长的链往上合并。具体的设\(f_{x,i}\)为当\(k=i\)时，在\(x\)处能取出的最

类似最小生成树，对边排序依次加上，但是数据大，要进行离线处理，存起来，将比他小的边加上，判断连通用并查集（路径压缩，按秩合并）。唐完的我在赛时没写按秩，而且while没写终止条件（唐老鸭）。先按秩后合并，测评机有点玄学但确实要这样。初版：#include<bits/stdc++.h>usingnamespacestd;cons

题目一 ​​​​Problem-2196大致意思就是求每个点为根的最大深度；对于这个问题，很快速的我们可以想到跑两次dfs，第一次预处理出以u为根的子树的第一，二深的深度，第二次dfs进行树形dp，从u->v时推出v的最大深度，用up[v]来存储；代码如下：注意分走到第一大和第二大的路径上的决策，以

题面传送门首先把树上最大独立集的dp抽象一下，可以得到如下做法：对于每个点求出\(b_i=\max(0,a_i-\sum\limits_{j\inson_i}b_j)\)，则所有\(b\)之和就是最大独立集。则我们设\(dp_{i,j}\)表示第\(i\)个点的\(b_i=j\)时的方案数，直接朴素的dp时\(O(nm^2)\)的。一个

题意：给出一个\(n\)个点的树，每个点有黑白两种颜色。初始时每个点都是黑色的。\(q\)次操作，支持：Cx将第\(x\)个点的颜色反转。G询问树上两个黑色点的最远距离。分析：尝试使用点分树，对于一条路径，可以从点分树的\(lca\)处统计，由于涉及到删除和添加两种操作，因此可以用mu

黑白染色树题意有一棵点数为\(n\)的树，树边有边权。给你一个在\([0,n]\)之内的正整数\(k\)，你要在这棵树中选择\(k\)个点，将其染成黑色，并将其他的\(n-k\)个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。

洛谷P3469BLO-Blockade题意给定一张无向图，求每个点被封锁之后有多少个有序点对\((x,y)(x\ney,1<=x,y<=n)\)满足\(x\)无法到达\(y\)。思路使用Tarjan求出割点，有以下几种情况。当前点不是割点，答案为\(2\times(n-1)\)，即该点与其他所有点不连通。当前点是割点，答案

考虑删除树上一条边\((u,v,l)\)，此时剩余部分构成两个连通块，如果不包含节点\(1\)的连通块中有Aoki选择的点，那个这条边的贡献至少为\(2l\)。简单构造发现，当Takahashi构造的路径恰好为Aoki选择的点和\(1\)构成的虚树时，能够取到路径长度的最小值。此时我们将题目转

FHQ-Treap概述FHQ-Treap，又名无旋Treap。显然，FHQ-Treap不使用旋转操作来维护平衡，他利用分裂和合并两个操作维护平衡。定义结构体放个代码constintN=1e5+10;inttot,root;structFHQ_Treap{intl,r,val,key,siz;}tr[N];#definelctr[p].l#definerc

超棒的贪心构造题。可以观察到每次操作的两个叶子，充要条件是路径上匹配边和非匹配边交替出现，操作完后全部取反。首先考虑答案上界，从是否能取到上界入手，是本题的突破口。考虑操作两个叶子\(x,y\)，收益为\(dep[x]+dep[y]-2dep[\text{LCA}(x,y)]\)。若固定根\(r\)，当\(\text

树形dpP3177[HAOI2015]树上染色初看此题时，dp状态很明显是两维，但是合并子树时答案难于统计，然后……就不会了qwq。既然不通，考虑改变dp数组的含义，记\(dp_{i,j}\)表示当前\(i\)的子树中将\(j\)个点染黑对总答案的贡献。但是这样直接计算两点距离就变得更难了，考虑两

前言最简单的一次，终于AK了ABC，纪念一下。思路看到题目中有一句加粗的话入力で与えられるタイプ$3$のクエリの答えは$10^{18}$以下であることが保証されています。翻译出来是对于所有操作\(3\)，答案不超过\(10^{18}\)。首先，\(a_i\)一定不会是\(0\)，考虑一种情况，

MyBlogs[ARC183D]KeepPerfectlyMatched这场不打感觉亏麻了，怎么大家都不会D。首先匹配路径长度之和最大，很典的想到取重心，猜测答案上界\(\sum_idep_i\)可以取到。取完重心之后，希望不断把两个不同的子树里的点进行匹配，直到删空。因为原树本身存在完美匹配，所以找一对不同子