长链剖分总结
长链剖分，顾名思义，就是按照链长（即深度）把树剖成若干条链。具体的，定义每个点的儿子中，子树深度最大的点是重儿子，不断跳重儿子形成的链也就是重链。
长链剖分的性质：
1.从一个点向上跳重链的次数不会超过\(\sqrt n\)次。
证明：考虑每跳到一条新的链上，这条链一定比前一条链长，而最坏情况下，才有重链长度分别为\(1,2,3,\cdots\sqrt n\)，因此最多不会跳超过\(\sqrt n\)条重链。
2.任意一个点的\(k\)级祖先所在的重链的长度大于等于\(k\)
证明：如果\(k\)级祖先所在的链长度小于\(k\)，又因为这个点到\(k\)级祖先这条链已经长于原先的重链了，而这是不可能的，故任意一个点的\(k\)级祖先所在的重链的长度大于等于\(k\)。
长链剖分的应用
1.\(O(n\log n)-O(1)\)求树上\(k\)级祖先
根据刚刚的性质，我们令\(k'=\frac{k}{2}\)，那么\(x\)的\(k'\)级祖先所在的重链长度不小于\(k'\)，那么就可以知道\(x\)的\(k\)级祖先在条重链上了，然后我们预处理出倍增数组和小于链长次祖先，询问时就可以做到\(O(1)\)了。
例题：
2.优化和深度有关的树形DP
思路类似\(\text{dsu on tree}\) ,每次从重儿子那里继承信息，再额外计算轻儿子的贡献。
例题：
题意：给定一棵有\(n\)个节点的树，设\(d(x,k)\)为点\(x\)的子树内与\(x\)距离为\(k\)的点数，对于每个点，求出使\(d(x,k)\)最大的\(k\)中最小的一个。
思路：考虑一个\(O(n^2)\)的DP，设\(f_{x,i}\)表示\(x\)的子树里与\(x\)距离为\(i\)的点的个数，转移时\(f_{x,i}\leftarrow f_{y,i-1}\)。我们尝试优化，即先从重儿子那里继承信息，再把轻儿子的信息暴力合并上去。我们可以发现，如果只看重儿子的话，那么就相当于把\(f_{y}\)错位对应上了\(f_{x}\)，那我们就可以利用一种特殊的技巧，即动态分配DP数组的内存。具体来讲，我们为每条长链链顶申请长为链长的空间，然后链上的所有点共用这部分空间，即\(f_{y}\)的起点是\(f_{u}+1\)，那这样就可以把时间和空间都减到\(O(n)\)的量级。这时我们再考虑把轻儿子的答案，合并上来，这样的复杂度也是\(O(n)\)的，因为每一条重链只会被合并一次，而且每一次合并是\(O(len)\)的（len是链长），总共加起来就是\(O(n)\)的。这样我们就成功地把\(O(n^2)\)优化到了\(O(n)\)。
题意：求树上选择两两距离相等的3个点的方案数。
思路：先考虑朴素DP。设\(f_{x,i}\)表示点\(x\)的子树内与\(x\)距离为\(i\)的点的数量，\(g_{x,j}\)表示\(x\)的子树内满足\(d(u,lca(u,v))=d(v,lca(u,v))=d(x,lca(u,v))+i\)的点对数量，因此有转移：
\[ans\leftarrow f_{x,i-1}\times g_{y,i}\;,\;ans\leftarrow g_{x,i+1}\times f_{y,i}\;,\;f_{x,i}\leftarrow f_{y,i-1}\;,\;g_{x,i+1}\leftarrow g_{y,i}+f_{x,i+1}\times f_{y,i} \]可以发现，\(f_x,g_x\)可以像上一道题一样直接从\(f_y,g_y\)移一位得到，那自然也可以用动态分配内存来优化，只是注意\(g_{son_x}=g_{x}-1\)意味着之前要多申请一倍空间。
题意：多次询问，给定\(a,k\)，求树上满足\(dis(a,b)\leqslant k\)，且\(a,b\)都是\(c\)的祖先的点对\((b,c)\)的数量。
思路：这道题有114514种做法，之前用的是\(O(n\log n)\)的离线树状数组的做法，这里给出一个长剖的\(O(n)\)的做法。
首先考虑\(b\)不在\(a\)子树里的情况，这时\(b\)只能是\(a\)的祖先，那答案自然就是\(\min(dep[x]-1,k)\times(siz[a]-1)\)。
然后就是\(b\)再\(a\)子树里的情况，这时的贡献就是\(\sum\limits_{dis(a,b)\leqslant k}siz[b]-1\)，看起来这个东西也可以类似地维护，只是需要维护重链上的后缀和，这样转移时就可以直接错位继承了。复杂度\(O(n)\)。
标签：总结,长链,剖分,链长,祖先,leftarrow,重链 From： https://www.cnblogs.com/Xttttr/p/17262667.html