长链剖分

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

有以下性质：

• 一个节点的 \(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 与深度有关时才这么做，这样暴力合并的复杂度才不会超过链的总长。