【做题记录】ds合集 Part I

MiniLong / 2024-10-23 / 原文

ds 合集的 Part 1，此合集包含树上问题和图上问题。

树上问题

CF418D

题目链接

首先可以倍增找到 $(u,v)$ 中间的断点 $t$（ $t$ 和左边都去 $u$，右边都去 $v$）。然后就可以把树分成两部分（这里注意如果 $t=lca(u,v)$ 不能直接取子树），然后就是求 $\max(dis(u,S1),dis(v,S2))$。问题就是点到一个联通块的距离，且这个联通块是一个完整子树或树减去子树，在 dfn 序上至多分成两个区间。这个问题就随便做了，可以离线下来树上扫描线，也可以直接在 dfn 序上合并直径（最大距离一定是到直径两端点之一），或者树剖维护都可以。复杂度 $\Theta(n\log n)$。

CF741D

题目链接

其实就是求经过每个节点 $u$ 且两端在 $u$ 子树中的最长合法路径。一个路径合法当且仅当不超过一个字符出现奇数次，考虑将出现次数的奇偶性状压，那么就是找 $u$ 中两个不同子树的点对，满足它们到根的路径状态异或和的大小不超过 $1$，记录一下每个点的深度和状态，枚举奇数的位置就行，dsu on tree 处理，开个桶记录 $2^{22}$ 个状态就行。复杂度 $\Theta(nc\log n)$。

CF763D

题目链接

不同构肯定树 hash，考虑树上扫描线，维护所有子树的 hash 值的桶。每次根从 $u$ 转移到 $v$ 时，会删掉以 $u$ 为根的整棵树，加入以 $v$ 为根的整棵树，加入以 $u$ 为根除了 $v$ 子树以外的树。map 记录出现次数就行，复杂度 $\Theta(n\log n)$。

CF776F

题目链接

考虑这些区域会形成一棵树，可以暴力处理一下编号。然后就是在一棵树上染色，考虑从小往大染色。颜色是 $1$ 的显然只有一个点 $u$，那么颜色是 $2$ 的点在 $u$ 的所有子树中都不能超过一个，颜色为 $3$ 的点可以在颜色 $2$ 到 $u$ 的路径上，也可以在颜色 $2$ 的子树中。发现这个东西很像点分治的形式，于是模仿点分治，将每层都染成同一个颜色，个数不超过 $\Theta(\log n)$。复杂度 $\Theta(n\log n)$。

CF925E

题目链接

假设树上每个点的权值是 $a_i$，初始 $a_i = t_i$。那么变成黑点相当于链减 $1$，变白点相当于链加 $1$。现在就是要支持：区间加减 $1$，单点标记，询问全局没标记的点小于 $0$ 的个数。这个可以分块 $\Theta(n\sqrt{n} \log n)$ 做，空间 $\Theta(n\sqrt{n})$ 类似这题。但是考虑 $\Theta(n\sqrt{n})$ 的做法，空间线性。直接对询问分块，考虑将每 $B$ 个询问一起做，那么记录每个点在前面处理完之后的权值 $a_i$，然后考虑这 $\Theta(B)$ 个点的贡献。将这 $\Theta(B)$ 个点建虚树，每条边加的值都相等，那么将每个点都挂到它所在的虚边的深度大的那个点上然后排序，然后每次链加可以暴力跳祖先 $\Theta(B)$ 个点，然后再对每条虚边记录指针 $pos_i$ 为当前第一个 $<0$ 的位置，每次加会使指针移动 $\Theta(1)$ 个位置（因为只会 +1 或 -1）。排序部分可以把 $n$ 个点放到一起基数排序，然后复杂度就是 $\Theta(n\sqrt{n})$ 了。

CF833D

题目链接

路径数数考虑点分治，那么就是要考虑一堆三元组 $(val,x,y)$ 表示路径的权值积，黑色点 $x$ 个，白色点 $y$ 个。那么就是要找一堆三元组对，$(val1,x,y),(val2,a,b)$ 满足 $\dfrac{1}{2} \le \dfrac{a+x}{b+y} \le 2$，化简一下就是

\[\left\{ \begin{array}{**lr**} 2a-b\ge y-2x \\ 2b-a\ge x-2y \end{array} \right. \]

设 $x_i = 2a-b,y_i = 2b-a$ 为询问点，$x_i = b-2a,y_i = a-2b$ 为插入点，那么就是要对每个询问点找到所有 $x_j \le x_i,y_j \le y_i$ 的乘积，可以简单二维数点。那复杂度就是 $\Theta(n\log^2 n)$，但是直接搞会算两次，就成平方了，然后可以写个 cdq 三只 $\log n$，还是能过。

CF986E

题目链接

把每个数的所有质因子找出来，然后对每种质因子用动态开点线段树维护，然后询问枚举 $w$ 的因子搞，暴力这样做是 $\Theta(n\log^2 n \log V)$ 的，无法通过。发现不用树剖，其实就是要求 $\Theta(n\log V)$ 次一个点到根上含有 $p$ 质因子的有多少个。考虑离线，考虑对每个质因子单独处理，把 $w$ 的所有质因子 $p$ 处挂 $u,v,lca(u,v),fa(lca(u,v))$ 四个询问，然后把所有含有 $w$ 质因子的点拿出来，子树加，单点查即可。复杂度 $\Theta(n\log n \log V)$。

CF983E

题目链接

先考虑每个询问暴力做，发现把 $(u,v)$ 的路径拿出来，一定是先坐一个能走最长的车，再换乘，直到走到 $v$。如果 $v$ 是 $u$ 的祖先肯定很好做，就是从每个点往上一直走，首先预处理从每个点往上坐 $1$ 条线走到最远哪里，这个可以把每个路径的 $u,v$ 处插入一个插入标记，在 $lca(u,v)$ 插入一个删除标记，然后直接线段树合并就能做到单 $\log$。然后就是倍增处理走 $2^i$ 步最浅到哪，两边同时跳到 $lca$ 下面的点，然后看看是否有路径在 $(u',v')$ 子树中，就是个二维数点，主席树线段树合并随便做就行。复杂度 $\Theta(n\log n)$。

CF1039D

题目链接

注意到路径不能重复，所以考虑根号分治。当 $k \le B$ 时，考虑单次暴力，设二元组 $f_u$ 为 $u$ 的子树中能选出多少条长度 $k$ 路径，且满足第一关键字的情况下能有最多多少从根往下的空白。显然 $\Theta(n)$ 做即可，复杂度 $\Theta(nB)$。当 $k > B$ 时，此时答案不超过 $\dfrac{n}{B}$，且答案有单调性，所以考虑对于每个答案，二分它的边界，用上面的方法暴力验证，复杂度 $\Theta(\dfrac{n^2 \log n}{B})$。当 $B$ 取 $\sqrt{n\log n}$ 时，有最优复杂度 $\Theta(n \sqrt{n\log n})$。

CF1083C

题目链接

考虑从 $mex$ 入手，怎么判断权值为 $[0,i]$ 的区间是否组成一个链。判断若干个点是否组成一条链当然可以使用线段树来合并，把左右儿子组成的链的 $4$ 个点拿出来，枚举这个新链的两个端点，判断其他两个点是否在这条链上（就是 $dis(x,u)+dis(x,v)=dis(u,v)$）就行，然后再套个线段树二分，复杂度 $\Theta(n\log n)$。

CF1088F

题目链接

首先感觉一下，发现重构出来的树以最小权值作为根时，也应该是父亲权值小于儿子的。因为如果父亲权值大于儿子，那么我可以找到深度最大的这样的点，删掉这个点和它父亲的连边，把它接到原本树上的父亲上（由于这个深度是最大的，所以子树肯定没有它原本树上的父亲），通过这样的调整一定更优，于是就可以调整成一个父亲权值小于儿子的了。那么就是考虑连到比它小的点，如果连到一个不是祖先的点，那么找到这个点和它的 $lca$，这个 $lca$ 的权值比它们都小，而且距离更近，所以肯定更优。那么就是在原树上找到一个祖先连边了，直接枚举 $\lceil \log_2 dis(u,v)\rceil$，把 $u$ 到根的链分成 $\Theta(\log n)$ 段，然后在每个段上找到一个最小值连就行，其实就是这个段最顶上那个点，就是 $u$ 的 $2^k$ 祖先（注意一下边界），权值是 $a_u + \min a_v (1+k)$。倍增处理即可，复杂度 $\Theta(n\log n)$。

P2056

题目链接

每个点点权 $\in \set{0,1}$，每次翻转单点，求两个 $0$ 的距离最大。

最大距离考虑直径，线段树维护每个区间的直径，由于边权非负，可以贪心合并。（大区间的直径端点一定在左右儿子的 $4$ 个端点中取）复杂度 $\Theta(n\log n)$，不支持负边权。
动态查询路径考虑动态点分治，用堆维护每个点 $u$ 子树（点分树）中到父亲（点分树）的所有距离 $q_u$，用堆 $son_u$ 维护 $u$ 到所有儿子（点分树）的距离（这是将每个 $q_v$ 中最大的放进来，每个子树只放一个），再用一个全局的堆 $st$ 维护所有 $son_u$ 最大和次大的和。注意堆要支持删除，就对每个堆再开一个删除的堆（把删除的东西放入），取出时若两个堆顶相同就同时弹出。修改先删 $q$，然后更新 $son_{fa}$，然后再更新 $st$。复杂度 $\Theta(n\log ^ 2 n)$，支持负边权。
最大距离考虑括号序列，dfs 进入一个点塞 $($，然后塞点编号，然后出来的时候塞 $)$。显然两点距离就是删除匹配的后 $)))((($ 的长度。考虑线段树维护每个点的 $r_u,l_u$ 表示删除匹配后这段区间的右括号、左括号个数，和最长长度 $dis$。转移如下
- $r_u = r_{ls} + \max(0,r_{rs} - l_{ls}),l_u = l_{rs} + \max(0,l_{ls} - r_{rs})$。
- $dis_u = \max(dis_{ls},dis_{rs},\max\limits_{i\le mid <j} r_{[i,mid]} + |l_{[i,mid]}-r_{[mid+1,j]}|+l_{[mid+1,j]}) $
  - $\max\limits_{i\le mid <j} r_{[i,mid]} + |l_{[i,mid]}-r_{[mid+1,j]}|+l_{[mid+1,j]} =\max((l_{[i,mid]}+r_{[i,mid]})+(l_{[mid+1,j]} - r_{[mid+1,j]}),(l_{[mid+1,j]}+r_{[mid+1,j]})-(l_{[i,mid]} - r_{[i,mid]}))$
- $addp_u = \max l_{[l,i]}+r_{[l,i]}=\max(addp_{ls},\max(r_{ls}+l_{ls}+subp_{rs},r_{ls}-l_{ls}+addp_{rs}))$
- $adds_u = \max l_{[i,r]}+r_{[i,r]} = \max(adds_{rs},\max(l_{rs}+r_{rs}-subp_{ls},l_{rs} - r_{rs}+adds_{ls}))$
- $subp_u = \max l_{[l,i]} - r_{[l,i]} = \max(subp_{ls},l_{ls} -r_{ls}+subp_{rs})$
- $subs_u = \max l_{[i,r]} - r_{[i,r]} = \max(subs_{rs},l_{rs} - r_{rs}+subs_{ls})$
- 复杂度 $\Theta(n\log n)$，不支持负边权

CF1413F

题目链接

记录 $sum_i$ 为 $i$ 到根的边权异或和，那么就是要找到两个点使得它们 $sum_u = sum_v$ 且 $dis(u,v)$ 最大，且支持区间翻转。考虑用 P2056 直径的思路记录线段树每个节点 $sum=0/1$ 的直径，翻转的时候交换一下 $tr_{u,0},tr_{u,1}$ 即可。复杂度 $\Theta(n\log n)$。

CF1479D

题目链接

路径数颜色，考虑主席树记录每个点到根的每个颜色出现次数模 $2$。如果出现了偶数次就是根到 $u$ 和根到 $v$ 的次数模 $2$ 异或起来是 $0$。可以考虑在主席树上二分找这个 $x$，那么就是要快速判断一段区间的颜色是否按位异或起来都是 $0$。用个异或哈希刻画这个东西就行了。复杂度 $\Theta(n \log n)$。

BZOJ3252

题目链接

先考虑一个一个取是不是对的。显然是对的，因为如果一条路径在前两次没被选而被第一次选了，那么第一次肯定可以拿第二次的更优，矛盾了。那么再考虑贡献不能重复算怎么办，设 $maxn_u$ 为从 $u$ 到 $u$ 子树的一个叶子最长的一条路径（也就是长链），那么当 $u$ 子树里有被选的点时，$maxn_u$ 一定被选了，而且是第一次选 $u$ 子树内的点时就被选了，所以其他点不可能有 $u \to maxn_u$ 这条链上的贡献了。那么一个叶子的贡献就是它到它所在长链链顶的权值和，选出前 $k$ 大的即可，复杂度 $\Theta(n\log n)$。

CF526G

题目链接

这题是真牛。

考虑单次询问，那么把 $x$ 设为根，显然这 $y$ 条路径都是 $y$ 对叶子节点构成的，那么再考虑任意 $2k$ 个叶子是否存在一个构造使得能覆盖它们的虚树呢？答案是肯定的。把它们按照 dfn 序排序，每次把首尾配对即可。那么不考虑包含 $x$，就是要求选 $2k$ 个叶子使得它们构成的虚树权值和最大，这里可以运用 BZOJ3252 的长链剖分的做法 $\Theta(n)$ 做，然后如果不包含 $x$，即它们都在 $x$ 的同一棵子树里，那么删掉贡献最小的那个点，加上 $x$ 其他子树到它距离最大的那个就好了。这样单次询问就可以在 $\Theta(n)$ 的复杂度内搞定。

考虑多次询问，每次询问的瓶颈在于每次都要长剖一次，很劣。我们发现每次距离 $x$ 最远的那个点，也就是直径的端点，一定会被选。所以，不妨把直径的两个端点分别作为根求答案取最大值。再额外选 $2y-1$ 个叶子，可以预处理出来选前 $i$ 个叶子的答案，与 BZOJ3252 一模一样。然后不包含 $x$ 的话证明 $x$ 所在长链一定不是前 $2y-1$ 个，所以可以删掉第 $2y-1$ 个换成 $x$ 的长链能让损失最小。但是考虑 $x$ 往上第一个遇到的长链，若把它去掉，$x$ 的长链还会额外贡献那条长链在 $x$ 到根这部分的长度，可能更优。所以再判断删除第 $2y-1$ 条链和 $x$ 往上第一条长链哪个更优就行。后者可以倍增找到，记录每个点被覆盖长链的排名就行。复杂度 $\Theta(n\log n)$。

CF1633F

题目链接

考虑有完美匹配的充要条件，就是 $\sum\limits_u [2 | siz_u] = \sum\limits_u [2 \nmid siz_u]$，且只会选择每个 $2\nmid siz_u$ 的 $(u,fa_u)$ 这些边。每次加入一个相当于把它到 $1$ 的路径上全部翻转奇偶性，用线段树维护每个区间的奇数、偶数 $siz_u$ 个数和每个奇数的 $siz_u$ 的 $id(u,fa_u)$ 之和，每次翻转直接交换奇偶即可，树剖维护一下，复杂度 $\Theta(n\log^2 n)$。

CF1654G

题目链接

贪心地走，一定是走到一个点 $v$ 使得 $v$ 有相邻同高度的点，然后反复跳再下去，就是 $2h_u - h_v$。那么要最小化 $h_v$。考虑这样的 $v$ 的种类数量，因为每当出现一个两个高度为 $t$ 的相邻的点，就一定底下会多出来 $2t$ 个点，注意到是树形结构，所以 $\sum h_v = \Theta(n)$ 的。那么 $h_v$ 就有 $\Theta(\sqrt{n})$ 种，设 $f_{i,j}$ 是从 $i$ 开始走到一个高度为 $j$ 的 $v$ 所需要初始最小动能。先从低往高转移，然后每个相同高度的联通块换根转移。复杂度 $\Theta(n\sqrt{n})$。

CF1749F

题目链接

考虑到 $d$ 很小，不妨将所有更改挂到对应节点上，然后枚举查询节点的不高于 $d$ 级祖先。

更改时，先考虑 $lca(u,v)$ 子树内的贡献。可以开 $20$ 棵线段树维护每个距离的标记。对于链 $(u,v)$，可以在这条路径上每个点在 $[1,d]$ 这些线段树上加上 $k$，但是这样会算重，具体地，对于一个点 $x$，若它还有儿子 $y$ 被更改，那么 $y$ 子树中距离 $y$ 不超过 $d-1$ 的点会被多加 $k$。所以对于链 $(u,v)$ 上除了 $lca(u,v)$ 的点之外所有点都在 $[1,d-1]$ 这些线段树上减 $k$。查询的时候枚举 $u$ 的 $20$ 个祖先然后单点查询。这样复杂度是 $\Theta(nd\log^2 n+nd\log n)$，不平衡。注意到只是单点查，那么树上差分一下变成子树查询即可，复杂度 $\Theta(nd \log n)$。然后是 $lca(u,v)$ 子树以外的贡献，那么考虑直接枚举 $lca(u,v)$ 的不超过 $d$ 级祖先，在每个这样的点 $x$ 开 $20$ 个标记，表示 $x$ 子树到 $x$ 距离等于 $i$ 的标记。类似地，每次把 $tag_{x,0}$ 到 $tag_{x,d-dis(u,lca(u,v))}$ 加上 $k$，设 $x$ 在 $lca(u,v)$ 方向儿子为 $y$，把 $tag_{y,0}$ 到 $tag_{y,d-dis(u,lca(u,v))}$ 全部减去 $k$ 即可。复杂度 $\Theta(nd^2)$（当然可以做到 $\Theta(nd\log d)$）。

查询直接枚举 $u$ 的 $20$ 个祖先，然后子树求和就行，再加上标记，复杂度 $\Theta(n(d\log n+d))$。

所以总复杂度为 $\Theta(nd(\log n + d))$。

CF1810F

题目链接

注意到答案应该不会超过 $\max a_i +\log_m{n}$，因为可以构造一个完全 $m$ 叉树。于是考虑枚举答案，然后来验证。设当前答案为 $ans$，显然先搞出来个深度为 $ans$ 的满 $m$ 叉树比较优，然后从后往前枚举值域 $i$，设当前空位为 $x$，每次使得 $x \leftarrow m(x - cnt_i),i\leftarrow i - 1$。若 $x$ 始终 $\ge 0$，那么就可行。考虑线段树维护这个东西，设每个区间要合法初始值最小为 $f_u$，使用最小初始值最后剩下 $g_u$，从 $l$ 到第一个有数值的位置设为 $tr_u$。合并的时候若 $m^{len_{ls} - tr_{ls}}g_{rs} \ge f_{ls}$，那么 $f_u = f_{rs},g_u = g_{ls}+m^{len_{ls}}(g_{rs} - f_{ls})$。否则设 $t=\lceil \dfrac{f_{ls}-m^{len_{ls} - tr_{ls}}g_{rs}}{m^{len_{ls} - tr_{ls}+tr_{rs}}} \rceil$，那么 $f_u = t+f_{rs},g_u = g_{ls} + m^{tr_{ls}}(g_{rs}+t\cdot m^{len_{ls} - tr_{ls}+tr_{rs}}- f_{ls})$。每次单点改即可，复杂度 $\Theta(n\log n)$。

CF1827D

题目链接

注意到有两个重心当且仅当存在一条边使得两个端点的子树 $siz$ 相等且等于 $\dfrac{n}{2}$。如果直接维护就是要维护 $\min |n-2siz_i|$，还要区间加 $1$ 减 $1$，比较麻烦。考虑这个点会在哪，感受一下发现肯定是在已经有的重心旁边，那么答案就是 $n-2maxson$，再更新一下重心就行（只会移动一步）。直接树剖维护，复杂度是 $\Theta(n\log^2 n)$。

但是可以单 $\log$，具体地，设重心在 $x$，$maxson=k$，$id$ 为 $k$ 的编号。若加的是 $id$ 的子树里的点，判断 $id$ 是否能成为重心，如果可以 $id' \leftarrow x,k\leftarrow \dfrac{n}{2},x\leftarrow id$，不然就是 $k \leftarrow k+1$。如果不在 $id$ 子树判断这个子树是否比 $id$ 子树更大，更新一下就行。用树状数组维护单点加，区间和，复杂度 $\Theta(n\log n)$。

CF1904F

题目链接

注意到每个点点值不同，那么把小的连到大的，要求是个 dag 就行。用线段树优化建图，复杂度 $\Theta(n \log^2 n)$。

CF1935F

题目链接

显然每次连边只可能是 $(x,x+1)$，且最多只有一次是 $(x,x+2)$。那么对于每个 $(x,x+1)$，当前仅当它们在一个点的两个不同子树中时有用，于是把 $(x,x+1)$ 挂到 $lca(x,x+1)$ 上，每次用并查集合并。然后子树的父亲的可以记录每个 $sum_u$ 为 $u$ 子树中最浅的 $lca(x,x+1)$，如果 $u$ 的儿子 $v$ 的 $sum_v$ 深度比 $u$ 浅就可以连，然后如果还不联通的话就要连 $(u-1,u+1)$。复杂度 $\Theta(n\log n)$。

CF1976F

题目链接

经典题。考虑根度数是 $1$，所以第一次肯定是选从根开始的一条路径，那肯定就是最深的那个叶子。然后第二次就可以选两个到根的链，也一定是两个叶子（选两个原因：有个经典结论是在树上选 $2k$ 个点一定存在 $k$ 条链并集是它们的虚树），这个就是 BZOJ3252，长剖之后每个叶子的权值就是它到链头的长度，排个序就好了。复杂度 $\Theta(n\log n)$，瓶颈在排序。

图上问题

CF280D

题目链接

选 $k$ 个可以描述为一个费用流模型，可以模拟费用流来做，但我不会。注意到它是凸的，所以线段树维护 $k$ 大子段和，可以闵可夫斯基和合并。复杂度 $\Theta(nk\log n)$，有 $16$ 倍常数。

没过

CF757F

题目链接

以 $s$ 为起点求一遍最短路，把所有 $dis(v) = dis(u)+w$ 的 有向边 $(u,v,w)$ 保留，形成一个 dag。也就是要问这个 dag 上删掉一个点使得最多有多少与 $s$ 不连通的点。那就是求新图上起点为 $s$ 的支配树上除了 $s$ 的最大 $siz$ 是多少，直接建支配树求即可。复杂度 $\Theta(n\log n)$。

CF878C

题目链接

单次可以对每个项目排序，然后每个人连到第一个小于它的人，答案就是缩点之后每个入度为 $0$ 的 scc 的点数和。这个图还有个性质，就是它是一个链状物，一个点只可能连到链后面的点。所以加边的时候只有返祖边会寄。于是先按第一个项目把这条链求出来，加边的时候如果遇到返祖边就直接用个并查集把之间的点并起来。复杂度 $\Theta(nk\log n)$，用 set 维护。

CF811E

题目链接

因为一列是完整的，所以考虑用线段树维护维护两端的每个点所在的联通块编号。合并的时候先把中间的两列合并，然后再看左右两边是否有联通块被中间合并的时候一起合并了，并查集维护即可。

CF903G

题目链接

最大流=最小割。为了方便，设 $A_0 \to A_1,A_n \to A_{n+1}, w=0$， $B$ 同理注意到切在 $A,B$ 的边分别恰好割一条，设它们分别是 $x,y$。那么要付出的代价就是 $a_x+b_y + \sum\limits_{u_i \le x,v_i >y} w_i$。因为只有 $a_x$ 会改变，不妨先处理出来 $f_i = \min\limits_j b_j + \sum\limits_{u_k \le i, v_k > j} w_k$。考虑扫描线，初始每个位置 $j$ 的值为 $b_j$，然后扫 $i$，每遇到一个 $u_k = i$，把 $[0,v_k - 1]$ 加上 $w_k$，然后求全局 $\min$ 即可，就处理处理 $f$ 了。然后 $a_x$ 的话就用个 $set$ 维护单点改，全局 $\min$ 就行。复杂度 $\Theta(n\log n)$。

P4151

题目链接

注意到随便从 $s$ 走到 $t$ 搞个路径出来，然后可以任意选环。由于异或的性质，不需要把所有环都拿出来，那可以先搞出个 dfs 树出来，然后把每条非树边在上面形成的环搞出来做个线性基就行。复杂度 $\Theta(n\log n)$。

CF938G

题目链接

用 P4151 的结论，然后套一个线段树分治。考虑怎么维护 dfs 树，使用带权并查集，但是因为每次会 findrt，所以连的边不是真实的。那么在连 $(u,v)$ 时，先找到 $u$ 到根的异或和，和 $v$ 到根的异或和，把 $w$ 异或上它们，再连就行。复杂度 $\Theta(n\log n(\log n + \log V))$。

P7520

题目链接

建出支配树，发现如果一个点会改变那么它的子树也会被改变。那么预处理每个点删了它父亲在原图的反图能走到哪些点，查询就查除了 $1\to u$ 的路径的那些点就行。复杂度 $\Theta(n(n+q))$。

CF1348F

题目链接

考虑构造一组解，贪心地，按右端点、左端点排序，每个区间取最左边能取的值，用个 set 维护。考虑怎么搞两组解，感受一下就可以发现遇到一个区间，它本来还能取到更往左的值，但是已经被取了，那么就可能与那个先取的那个区间交换。具体地，考虑设 $L_i$ 为排列中的值 $i$ 其被取的区间左端点，$R_i$ 为右端点。那么考虑从小到大枚举每个值，就是要找到一个 $L_i \le j<i\le R_j$，那么扫到一个值的时候往 $R_i$ 处插入 $i$ 以便到时候删除，然后用个 set 维护插入删除，每次二分找到一个 $\ge L_i$ 的可以了。复杂度 $\Theta(n\log n)$。

CF1419F

题目链接

先把 $n$ 个点连边排序，依次加边。注意到一个点只能走到 $4$ 个不同的位置，所以当且仅当现在只有 $\le 4$ 个联通块时可能存在。所以当第一次只剩 $4,3,2$ 个联通块时判断一下，这里最多只有 $3$ 种情况。每次可以考虑枚举两个 $x,y$ 都不同的点，算出它们所在长方形的其他两个点，把这两个点标记上枚举的这两个点分别所在的联通块（在这些点上记录每个联通块到它最短距离），然后找到一个最优的点满足所有联通块到它的最远距离最小，更新答案。注意到有 $2$ 个联通块的时候不一定有上述情况，所以可以枚举两个点算它们之间的距离即可。具体可以使用 dsu 实现，复杂度 $\Theta(n^2 \log n)$。

CF1439B

题目链接

考虑先把所有度数大于等于 $k$ 的点加入一个集合。然后计算出每个集合中的点邻居有多少个，然后如果有点邻居小于 $k$，那就把它删了。可以用堆维护，重复这个过程，最后如果有剩下的那就是第一合法的子集。考虑团怎么求，相似地，我们可以考虑枚举每个度数大于等于 $k-1$ 的点，重复上面的过程，只不过把下限调整为 $k-1$。考虑如果没有 $k-1$ 的点的话上面的点集肯定能找到，所以这个团肯定包括一个邻居恰好 $k-1$ 的点，那么我们枚举这些点，暴力 $\Theta(k^2)$ 判断这些点的邻居是否组成一个团。注意到一个团有 $\Theta(k^2)$ 条边，而边集是 $\Theta(m)$ 级别的，所以合法的 $k$ 肯定不超过 $\Theta(\sqrt{m})$，且邻居有 $k-1$ 个点的点最多有 $\Theta(\dfrac{m}{k})$ 个，所以复杂度为 $\Theta(mk)$ 即 $\Theta(m\sqrt{m})$。实现的时候会多带个 $\Theta(\log n)$，因为要查找 $(u,v)$ 是否有边。使用 unordered_map 会很慢很慢。

CF1550F

题目链接

考虑两两连边，求出 mst，那么 $k$ 就要大于 mst 上路径边权最小值。考虑使用 boruvka 算法，那么就是每次从一个点出发，问最近能走到哪个不在同一联通块中的点。那么就说要从每个 $u$ 开始，看看 $u-d,u+d$ 左右两侧第一个不和 $u$ 在同一联通块的位置。由于 $u-d,u+d$ 是固定的，所以可以预处理出来这两个位置左右的第一个点。然后每次迭代之后对于每个点求出 $L_i,R_i$ 表示左边和右边第一个和它不同的点。这样就能做到 $\Theta(n\log n)$ 了。

P6628

题目链接

考虑对每个 $i$ 单独处理就是要走一个 $s \to i$ 的欧拉通路。那么就说要考虑度数+连通性，因为连边是 $|i-j|$，所以任何 $(i,j)$ 都可以转化为 $(i,i+1),(i+1,i+2)\cdots (j-1,j)$。然后先把 $m$ 条边加进来，再加入一条 $(s,i)$ 的虚边，对于所有奇数点排序相邻连边。然后连通性也是类似，把相邻两个不连通的点的边加入，求 mst 就行。（加虚边不影响连通性是因为如果 $(s,i)$ 删了之后不在同一联通块，那么就有一个联通块有恰好 $1$ 个奇数点，显然不可能）复杂度 $\Theta(n\log^2 n)$。

CF1682F

题目链接

其实把所有 $b_i < 0$ 看成 $-b_i$ 个黑点，$b_i > 0$ 看成 $b_i$ 个白点，那就是两两匹配最短长度和。那其实就是每个点往前面第一个与它不同颜色没匹配的匹配。直接统计是可以，但是不太方便。考虑一个 $(a_i,a_i + 1)$ 的贡献，由于保证 $b$ 之和是 $0$，所以必定有 $sum_{i-1} - sum_{l-1} = -(sum_r - sum_{i-1})$。那么贡献就是 $(a_i - a_{i-1}) \cdot |sum_{i-1} - sum_{l-1}|$。那直接离线下来，二维数点即可，可以对 $sum$ 排序算 $[l+1,r]$ 之间的贡献，就可以用 bit 统计了。复杂度 $\Theta(n\log n)$。