是用于合并子树与深度相关的信息。由于每个点只会在一条长链中，每个长链又只会在他和他父亲的转移中被更新一个，所以复杂度线性。
以上算法比其他剖分优秀的点在于恰好适配了深度这一要素。
Dominant Indices
板题。
[POI2014]HOT-Hotels 加强版
\(n^2\) 很好想：存在且仅存在一个点使得以它为根，其他儿子的深度相同，所以换根 dp 就好了。
但是这个 dp 显然是扩展不了的。换个状态。但是我不会了。反正只能在一个根的环境下探究。
所以画个图研究一下形状，发现答案只会有两种。都在最上面的LCA处统计即可。
令 \(f_{i,j}\) 为 \(i\) 子树内距离为 \(j\) 的点的个数，\(g_{i,j}\) 为 \(i\) 子树内点对 \((x,y)\) 的个数，满足 \(d_{x,lca(x,y)}=d_{y,lca(x,y)}=d_{lca(x,y),i}+j\)。
然后直接转移即可。注意到 \(g\) 数组涉及右移，所以要留一点空间。
hydro3252. 攻略
注意到这里或许存在一个很经典的贪心：每次找最长链。
所以维护所有的连通块和链就可以了。均摊线性。 感觉和长链剖分本身没什么关系啊。（？）