长链剖分
长链剖分是对于每一个点 uuu，求出它的重子节点 hhh，满足 hhh 的子树中最深的节点深度最大，连接 u→hu \rightarrow hu→h 这条重边。其他边为轻边。若干条首尾相连的重边叫做重链。如果把叶子节点也看做一条重链，那么整棵树就被划分为了若干条重链。
如图（来自 OI-WIKI）：
实现过程的伪代码如下：
性质
1. 从根节点到叶子中，最多有 O(n)O(\sqrt{n})O(n ) 条轻边。
> 设从根节点到叶子共有 kkk 条轻边，我们从叶子开始向根跳，设 did_idi 表示当跳了 iii 条轻边到节点 uuu 之后，maxv∈son(u)(depv−depu)\max_{v \in \operatorname{son}(u)}(dep_v-dep_u)maxv∈son(u) (depv −depu ) 的值。每沿着轻边向上跳 111 步，跳到的节点 uuu 的子树大小比刚才的节点 vvv 的子树大小至少增加了 du+1d_u+1du +1。也就是 du≥dv+1d_u \geq d_v+1du ≥dv +1。
> n≥∑di≥kd1+∑i=0k−1i=kd1+k(k−1)2≥k(k+1)2n \geq \sum d_i \geq kd_1+\sum_{i=0}^{k-1} i=kd_1+\frac{k(k-1)}{2} \geq \frac{k(k+1)}{2}n≥∑di ≥kd1 +∑i=0k−1 i=kd1 +2k(k−1) ≥2k(k+1) ，因此 k≤O(n)k \leq O(\sqrt{n})k≤O(n )。
不过这个没啥用，因为重链剖分是 O(nlogn)O(n \log n)O(nlogn) 的，严格优于长链剖分的 O(nn)O(n \sqrt{n})O(nn )。
2. 设 uuu 的 kkk 级祖先为 ppp，则 ppp 所在重链的长度不低于 kkk。
> 如果 p→up \rightarrow up→u 是重链，那么我们已经知道 p→up \rightarrow up→u 的长度等于 kkk。
>
> 如果 p→up \rightarrow up→u 不是重链，那么假设重链是 p→vp \rightarrow vp→v（vvv 为叶子），则该链的长度一定大于 p→up \rightarrow up→u 的长度，也就是大于 kkk。
例题1
P5903 【模板】树上 K 级祖先
> 给定一颗有根树，qqq 次求 uuu 的 kkk 级祖先。
常用的做法是 O(qlogn)O(q \log n)O(qlogn) 的，过不了。
设 iii 为自然数，2i≤k<2i+12^i \leq k<2^{i+1}2i≤k<2i+1，我们先求 uuu 的 2i2^i2i 级祖先 vvv，显然这是可以预处理倍增数组 O(1)O(1)O(1) 得到的。接下来，我们需要求 vvv 的 k−2ik-2^ik−2i 级祖先，由于 k<2i+1k<2^{i+1}k<2i+1，所以 k<2i+2ik<2^i+2^ik<2i+2i，即 k−2i<2ik-2^i<2^ik−2i<2i。设 LLL 为这条重链的长度，根据性质 2，L≥2iL \geq 2^iL≥2i，也就是 0≤k−2i<L0 \leq k-2^i<L0≤k−2i<L。我们跳到
vvv 所在链的顶端 ttt，设我们这个操作走了 xxx 距离，那么我们还需要向上跳 k−2i−xk-2^i-xk−2i−x 步。容易知道 −L≤k−2i−x≤L-L\leq k-2^i-x \leq L−L≤k−2i−x≤L，因此我们在每一个链的顶端 ttt 的位置维护两个数组 upiup_iupi 和 downidown_idowni ，分别表示从 ttt 向上 iii 步的点和从 ttt 沿着重链向下 iii 步的点，其中 i≤Li \leq Li≤L。总时间复杂度 O(nlogn+q)O(n \log n+q)O(nlogn+q)。
代码：
例题2
CF1009F Dominant Indices
> 给定一颗根为 111 的有根树，设 du,id_{u,i}du,i 表示在 uuu 的子树内到 uuu 距离为 iii 的点的数量，对于每一个 uuu，求使得 du,id_{u,i}du,i 最大的 iii，如果有多个取最小的 iii。
不难发现 du,id_{u,i}du,i 的计算方法：
du,0=1du,i=∑v∈son(u)dv,i−1d_{u,0}=1 \\ d_{u,i}=\sum_{v \in \operatorname{son}(u)} d_{v,i-1} du,0 =1du,i =v∈son(u)∑ dv,i−1
设 mmm 表示深度，这样做是 O(nm)O(nm)O(nm) 的。
考虑长链剖分，设 uuu 的重儿子为 hhh，轻儿子为 vvv。首先，我们利用指针，让 dhd_hdh 的值直接写到 du+1d_u+1du +1 上，更新答案 ansu=ansh+1ans_u=ans_h+1ansu =ansh +1；接着我们处理 vvv 的子树，用上面的暴力递推合并答案。
分析复杂度，对于轻儿子 vvv，我们合并答案的复杂度是 O(depv)O(dep_v)O(depv ) 的，也就是 vvv 所在重链的长度，而所有重链长度和为 nnn，因此时间复杂度为 O(n)O(n)O(n)。
代码：
通过本题可以发现，长链剖分可以用于优化复杂度和树高有关的 DP 问题。
例题3
P5904 [POI 2014] HOT-Hotels 加强版
> 给定一颗树，设 disti,jdist_{i,j}disti,j 表示 i,ji,ji,j 之间的距离，求有多少个无序三元组 (i,j,k)(i,j,k)(i,j,k) 满足 disti,j=distj,k=distk,idist_{i,j}=dist_{j,k}=dist_{k,i}disti,j =distj,k =distk,i 。
设 111 是根，mmm 表示最深深度，考虑朴素 DP。设 fu,if_{u,i}fu,i 表示在 uuu 子树内的点 vvv 中满足 distu,v=idist_{u,v}=idistu,v =i 的点 vvv 数量，gu,ig_{u,i}gu,i 表示在 uuu 子树内的点 x,yx,yx,y 中满足
distLCA(x,y),x=distLCA(x,y),y=distLCA(x,y),u+idist_{\operatorname{LCA}(x,y),x}=dist_{\operatorname{LCA}(x,y),y}=dist_{\operatorname{LCA}(x,y),u}+idistLCA(x,y),x =distLCA(x,y),y =distLCA(x,y),u +i 的无序对 (x,y)(x,y)(x,y) 数量。
假设现在搜索到了点 uuu，正在处理 uuu 的儿子 vvv，可以得到：
ans:=ans+∑ifu,igv,i+1+∑ifv,i−1gu,igu,i:=gu,i+gv,i+1+fu,ifv,i−1fu,i:=fu,i+fv,i−1ans:=ans+\sum_{i} f_{u,i}g_{v,i+1}+\sum_{i}f_{v,i-1}g_{u,i} \\ g_{u,i}:=g_{u,i}+g_{v,i+1}+f_{u,i}f_{v,i-1} \\ f_{u,i}:=f_{u,i}+f_{v,i-1} ans:=ans+i∑ fu,i gv,i+1 +i∑ fv,i−1 gu,i gu,i :=gu,i +gv,i+1 +fu,i fv,i−1 fu,i :=fu,i
+fv,i−1
边界条件：
fu,0=1f_{u,0}=1 \\ fu,0 =1
这样就是 O(nm)O(nm)O(nm) 的复杂度。考虑长链剖分，对于重儿子 hhh，我们让 fhf_hfh 直接写到 fu+1f_u+1fu +1 上，ghg_hgh 写到 gu−1g_u-1gu −1 上；对于轻儿子 vvv，直接暴力转移。
代码：
