长链剖分

类似于轻重链剖分，也有一种树链剖分方式叫做长链剖分，每次我们选子树深度最大的节点当做重儿子，注意这里子树深度是指一棵子树中所有结点的深度最大值。

有以下性质：

• 一个节点的 $k$ 级祖先所在链的长度一定大于等于 $k$。

比较显然。因为如果小于 $k$ 的话就会选从那个祖先到这个节点的路径当做重链。

• 所有链的总长是 $O(n)$

比较显然。因为重链不交，可以近似看做是对整个树的划分。

• 任意一个点向上跳跃重链的次数不会超过 $\sqrt n$ 次。

我们一直向上跳，每次跳到的一个点所在重链长度最小是上个点的重链长度加 $1$，所以我们一直经过的重链长度最多是 $1,2,…\sqrt n$，由此可知性质得证。

求 $k$ 级祖先

求 $k$ 级祖先，长链剖分可以做到 $O(n\log n)$ 预处理，$O(1)$ 查询。

具体做法如下：我们倍增处理所有结点的祖先，然后对于每个链，设链长为 $len$，处理出该链链顶向上，向下（顺着链向下）长度为 $len$ 的每一个点。这是预处理。

对一个查询，设为 $x,k$，表示我们要查询 $x$ 的 $k$ 级祖先，我们考虑设 $r$ 为 $k$ 的最高二进制位表示的那个二进制数，我们考虑寻找 $x$ 的 $2^r$ 祖先，由性质 $1$，我们可以得到这条重链的长度一定是大于等于 $2^r$ 的，这样我们就可以保证，我们要查询的点，一定是被我们预处理过了。所以我们可以通过判断被查询点和该链顶点的深度来进行 $O(1)$ 的查询。

长链剖分优化 dp

具体方法是，我们在合并信息的时候，直接把重儿子的承接过来，其余儿子的信息暴力统计，这样做的话时间复杂度是 $O(n)$ 的。

考虑证明。当一个儿子的信息被暴力统计时，这个儿子一定是其所在重链的链顶，那么合并这个儿子的信息的时间复杂度可以看做其所在重链的长度。

由此可以看出，总的暴力合并的复杂度不会超过链的总长，由此可以得到时间复杂度为 $O(n)$。

当然，大多是当这个 DP 与深度有关时才这么做，这样暴力合并的复杂度才不会超过链的总长。