简述
在常规树链剖分中把重儿子设成 \(siz\) 最大的儿子，这样从根跳重链时子树大小至少减半，因此只需要 \(O(\log n)\) 次即可到达任何节点。
考虑把关键字由 \(siz\) 改成子树内最大的深度 \(dep\)，这样的剖分方法称为长链剖分。
void dfs1(int u,int fa,int d){
dep[u]=d,mxdep[u]=dep[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs1(v,u,d+1);
if(mxdep[v]>mxdep[u]) mxdep[u]=mxdep[v],son[u]=v;
}
}
长链剖分具有一些性质：
-
从一个节点跳向链顶的父亲，所在的链长度一定增加，证明显然。
-
从一个节点跳链顶，\(O(\sqrt{n}) 次可以到达树根\)，结合上一性质可证，最坏情况是 \(1+2+\cdots+\sqrt{n}\)。但这个性质不常用。
优化 DP
大致思想
当 DP 的状态形如 \(f_{u,d}\)，只与子树 \(u\) 和子树内到 \(u\) 的距离 \(d\) 有关时，可以考虑长链剖分优化至 \(O(n)\)。
具体方法类似树上启发式合并，每次继承重儿子信息，轻儿子暴力合并。
复杂度证明：短链向长链合并时，长链长度一定不会增加，因此相当于把短链上的信息直接删去了。而一条链只会合并一次，每个节点只出现在一条链上，因此合并复杂度是 \(O(n)\) 的。
具体实现
难点在于如何继承重儿子的信息。
在绝大多数题目中，是一个 \(f_{v,d}\to f_{u,d+1}\) 的过程，也就是由父亲到儿子，距离增加 \(1\)。可以使用指针实现，先 DFS 预处理，对于根和每个轻儿子开子树内最大距离大小的空间，对于重儿子将指针设为父亲的指针位置加 \(1\)。
void dfs2(int u,int f){
if(u==1){
dp[u]=p,p+=mxdep[u]-dep[u]+1;
}
if(!son[u]) return;
dp[son[u]]=dp[u]+1;
dfs2(son[u],u);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f||v==son[u]) continue;
dp[v]=p,p+=mxdep[v]-dep[v]+1;
dfs2(v,u);
}
}
在一般情况下，每个数组大小就是 \(n\)。
也可以用 vector 实现，但是每次加入距离更小的，实际上是倒着存储，需要特判一些边界等等，且常数较大，不推荐。
在正式 DP 时，要利用好只能枚举短链上节点到 \(u\) 的距离。对每棵子树单独计数的题目，直接继承即可，且对于最值或求和之类的题目，会影响到的只有短链的范畴；对于多棵子树合并计数的题目，注意到一定有短链存在，因此还是以枚举短链上距离为依托。
例题
CodeForces-1009F Dominant Indices *2300
朴素的统计子树内距离对应节点个数。
重儿子可以直接继承，轻儿子暴力合并即可。
洛谷-P5904 [POI2014] HOT-Hotels 加强版
这类的三元组有两种：\(\mathrm{LCA}\) 是或不是重心的。
先考虑朴素 DP 怎么做，我们希望问题在子树内解决，所以要在 \(\mathrm{LCA}\) 处统计答案。
对于第一种情况，设 \(f_{u,d}\) 为 \(u\) 子树内距离为 \(d\) 的节点个数，\(g_{u,d}\) 为 \(u\) 子树内到 \(u\) 距离均为 \(d\) 且 \(\mathrm{LCA}\) 为 \(u\) 的点对数。
枚举每棵子树以及距离，统计答案的过程：
\[g_{u,d+1}\times f_{v,d}\to ans \]\[f_{u,d+1}\times f_{v,d}\to g_{u,d+1} \]\[f_{v,d}\to f_{u,d+1} \]对于第二种情况，设目标三元组 \((u,v,w)\)，有三部分组成：\(\mathrm{LCA}(u,v)\) 到 \(u,v\) 距离相等，均为 \(d_1\)，\(\mathrm{LCA}(u,v,w)\) 到 \(w\) 的距离 \(d_2\) 与到 \(\mathrm{LCA}(u,v)\) 的距离 \(d_3\) 无边集交且满足 \(d_1=d_2+d_3\)。
因为在 \(\mathrm{LCA}(u,v,w)\) 处统计答案，发现 \(d_3=d_1-d_2\)，因此 \(d_1-d_2\) 相等的位置本质没有区别，设 \(h_{u,d}\) 为 \(u\) 子树内满足这样情况且 \(d_1-d_2=d\) 的点对数，那么转移也类似上面了。
考虑怎么优化。
\(g\) 是只对一棵子树有效的，不需要继承，\(f\) 比较朴素的继承即可，而 \(h\) 比较不同，考虑到 \(v\) 到 \(u\) 后，\(d_1\) 不变而 \(d_2\) 增加 \(1\)，因此继承是形如 \(h_{v,d}\to h_{u,d-1}\)，与正常的继承不同。这就需要我们预处理指针时，把重儿子的指针设为父亲的指针减 \(1\)，从而空间要开 \(2\) 倍。
统计答案也需要精细处理，一个简单的想法是先计算轻子树之间的答案，这部分照搬暴力即可，同时要用一个临时数组记录一下当前统计到的 \(f,g,h\)。计算完之后，可以和重儿子继承来的 \(f,h\) 再合并得到另一部分的答案。
标签：长链,剖分,int,笔记,LCA,mathrm,mxdep From： https://www.cnblogs.com/SoyTony/p/Learning_Notes_about_Long_Chain_Tree_Decomposition.html