长链剖分是一种比较冷门的科技。算法本身很简单，就是把重链剖分中的权值（子树大小）变成子树内的最大深度。显然，长链剖分复杂度是 $O(n)$ 的，它和任何剖分一样，会把树剖分成 $O(n)$ 条链，并满足链长和 $O(n)$。

一般用来做下面两件事情：

树上 k 级祖先

以前写过，后来咕咕咕了的东西。

显然，我会倍增。复杂度 $O(n\log n + Q\log n)$ 。

但是长链剖分可以做到线性回答询问，复杂度可以是 $O(n\log n + Q)$ 。当然通过某些神仙科技（四毛子算法）可以做大 $O(n + Q)$ ，但是不会也与这篇 Blog 无关。

我们考虑长链剖分，并且在每个链顶端的位置记录一下这个链本身，以及这个链向上链长这么多级别的所有祖先。这个记录显然是 $O(n)$ 的。

然后是一个结论：

一个点的 $k$ 级祖先所在链的长度一定 $\ge k$

这个结论很显然，如果 $k$ 级祖先的所在链长度还不到 $k$ ，那剖分的时候为啥不往这个点的方向剖？

所以我们考虑，比如要查 $u$ 的 $k$ 级祖先，那么我们先向上跳 $r$ 步，满足 $2r > k \ge r$ 。设向上跳后到达的节点是 $y$ ，那么最后要查询的点一定在 $y$ 的链顶存储的点内。因为我们知道 $y$ 所在链长度一定 $\ge r$ ，而 $r > k - r$ ，所以在 $y$ 的链顶一定存储这个查询的目标。

于是我们就做到了 $O(1)$ 询问。

代码先咕一会。

与深度相关的 dp

长链剖分主要的用途还是在于合并以深度作为下标的信息。

这个过程是很类似 dsu on tree 的。我们考虑继承重儿子的信息，当然这个继承过程中深度显然需要移一位。然后再去合并其他子树的信息。

这样复杂度为啥是对的呢？我们考虑只有长链的顶端才会被拿去合并，其他点都是被继承。当我们在一个点 $u$ ，合并子树的过程中，其他子树的深度都是不超过当前点深度的，合并进来的时候是 $O(len)$ 其中 $len$ 是其他链的链长。不难发现，这样做了后总复杂度就是所有链的长度的和， $O(n)$。

但是为啥随机剖分会挂？我们考虑随机剖分的时候，同一个链可能会贡献多次。具体而言，可能出现长的合并进短的的情况，然后到父亲的时候又会拿这个长的来合并。复杂度是假的。

例题

k 级祖先模版： query on tree II

深度相关的dp ： 4.8模拟赛 C