DSU on Tree、长链剖分
树论
启发式合并（DSU on Tree）
总述
启发式合并是基于一种「观察」，将某些难写的在线算法转为离线的一种技巧，并不能说是一种「算法」。如不带修的树套树，都可以用 dsu on tree 水一水。
过程
- 遍历轻儿子，计算轻儿子的答案。清空轻儿子对记录数组的影响。
- 遍历重儿子，保留对记录数组的影响。
- 遍历轻儿子，加入轻儿子的所有贡献。
我们以一道例题来观察这一过程。
树上数颜色
给出 $n\le 10^5$ 个节点的树，每个点有颜色。求每个子树的颜色数量。
我们设 $cnt_i$ 表示颜色 $i$ 出现次数，$ans_i$ 表示 $i$ 子树的答案，根据如下操作：
- 遍历 $u$ 的所有轻儿子，计算相应答案 $ans_v$。遍历后删除所有影响。
- 遍历 $u$ 的重儿子，计算相应答案 $ans_w$。不用删除。
- 遍历 $u$ 的轻儿子，计算贡献。
|
|
复杂度及证明
-
任意一个点到根的轻边数量不超过 $\mathcal O(\log n)$。
-
出现一条 $u\to root$ 轻边，那么 $u$ 必然会被暴力统计一次。
对于每个点，最多被统计 $\mathcal O(\log n)$ 次，因此复杂度为 $\mathcal O(n\log n)$。
例题
CF246E Blood Cousins Return
板子题。
题意：$n\le 10^5$ 个节点的森林，每个点有颜色。$Q$ 次询问，每次询问 u d，求 $u$ 的 $d$ 级子孙颜色个数。
我们只需维护对应深度的颜色即可，用 multiset 维护。复杂度 $\mathcal O(n\log^2n)$。
树链剖分
长链剖分
性质
-
任意一点都属于且仅属于一条长链，故长链之和在 $\mathcal O(n)$ 级别。
-
任意一点到根的轻边数最大在 $\sqrt n$ 级别，也就是说从任意一点跳到根最劣复杂度是 $\mathcal O(\sqrt n)$。
- 假设当前链长为 $L$，使当前边为轻边，则必然有另一条边长度不小于 $L$。使节点最少，显然量级更大。不妨设另一条边为 $L+1$。假设底部到根有 $k$ 个轻边，那么其他长链长之和为 $\sum\limits_{i\in[1,k]} L_i$，而取极小时 $L_i$ 与 $L_{i+1}$ 之差 至少 为 $1$，因此 $\sum\limits_{i\in[1,k]}L_i\ge \sum\limits_{i\in[1,k]}i=\dfrac{k(k+1)}{2}$，故轻边数至多为 $\sqrt n$。
-
任意一点 $p$ 的 $k$ 级祖先 $q$ 所在的长链长度不小于 $k$。
- 若 $p$ 与 $q$ 在同一条链，则显然。不在同一条链，$p\to q$ 已经为 $k$，而其在另一条长链，则必然不小于 $k$。
应用
$\mathcal O(1)$ 在线查询 $k$ 级祖先
对于所有 长链链头 处理出其到 这条长链 上的所有子孙以及祖先，$k$ 级子孙记为 $son_{u,k}$，$k$ 级祖先记为 $anc_{u,k}$。由于链长 $len_i$ 和为 $n$，这部分复杂度为 $\mathcal O(n)$。并用倍增法求出所有点的 $2^k$ 级祖先，这一部分是 $\mathcal O(n\log n)$。
对于一组询问 $p\ k$，我们先求出满足 $2^{a}\le k<2^{a+1}$ 的 $a$，设 $p$ 的 $2^a$ 级祖先为 $q$。根据性质 2，$q$ 所在长链必然是不短于 $2^a$ 的。现在要求是 $q$ 的 $k-2^a$ 级祖先，而 $k-2^a<2^a\le len$。也就是说，所查询点要么在 $q$ 所在长链链头保存的子孙中，要么在长链链头保存的祖先中。那么直接查询即可。
优化以深度为维度的相关 dp
给定 $n\le 10^6$ 个点的树，设 $d(u,x)$ 表示 $u$ 子树中距离 $u$ 为 $x$ 的节点数。
对于每个点，求最小 $k$ 使 $d(u,k)$ 最大。
这不是 dsu on tree 板子吗我直接写不就行了
设 $f_{u,d}$ 表示 $u$ 子树中，$d$ 级子孙的个数。显然有方程：$f_{u,d}=\sum\limits_{v\in son(u)}f_{v,d-1}$。
长链剖分优化 dp 其实与启发式合并的做法类似，我们继承 重儿子的 $f$，$d$ 向后移一位即可，即 $f_u=f_{wson}+1$，这可以用指针实现。对于其他轻儿子，我们暴力合并即可。
每个点都属于一条长链，一个点作为链顶时才会被合并。而这个点的深度最长是其长链长度，因此合并的复杂度 $\mathcal O(\sum len)$，$len$ 是一条长链的长度，由性质 1 可得复杂度为 $\mathcal O(n)$。
具体实现就是对指针的应用了，这一步必须开动态数组，具体实现见代码。
|
|
例题
P5904 [POI 2014] HOT-Hotels 加强版
每个三元组可以分成如下两种类型：
- $(u,v,w)$ 共 LCA。
- $(u,v,w)$ 其二共 LCA。
设 $f_{i,j}$ 表示 $i$ 子树中与 $i$ 距离为 $j$ 的点的数量，$g_{i,j}$ 表示 $i$ 子树中，所有满足 $d(u,\operatorname{LCA}(u,v))=d(v,\operatorname{LCA}(u,v))=d(i,\operatorname{LCA}(u,v))+j$ 的点对 $(u,v)$ 数量。考虑子节点向父节点的转移，为了保证答案的不重复性，我们下面的 $u$ 表示的是合并完 $v$ 前的所有子树后的 $u$ 子树，下面的转移是 并行 的。
- 同一个子树中，直接继承：$g_{u,j}\gets\sum\limits_{v\in son(u)}g_{v,j+1}$
- 两个不同的子树，$f_{u,j}$ 是子树 $v$ 前的所有子树的答案：$g_{u,j}\gets\sum\limits_{v\in son(u)}f_{v,j-1}\times f_{u,j}$
- $f_{u,j}\gets\sum\limits_{v\in son(u)}f_{v,j-1}$
我们再考虑答案如何计算。
- $u$ 到 LCA 的距离恰好等于其余两点到 LCA 的距离：$ans\gets g_{u,0}$。
- 以 $u$ 为 LCA 的任意三点距离相等，分为 $u$ 的所有子树选点对以及子树 $v$ 选单点以及互换的情况，注意转移时也是与上面的转移并行的：$ans\gets \sum\limits_{v\in son(u)} f_{u,j}\times g_{v,j-1}+g_{u,j}\times f_{v,j-1}$。
这样 $\mathcal O(n^2)$ 的做法就能过 P3565 这道题的 easy version 了。
然后长剖优化一下，就可以 $\mathcal O(n)$ 过 hard version 了（就是这道题）。