概述
-
长链剖分通过把树剖成尽量长的多个链，高效地解决...我也不知道解决啥（长剖优化 DP 的东西在 DP 优化那边）。
-
毕竟这个东西，不具备启发式分裂的复杂度。不过其还是有一点性质的，有时候确实会用到...
-
恰如轻重剖是按 \(siz\) 选重儿子，长剖是按 \(dep\)（这里指当前子树的最大深度）来选长儿子，其余部分相同。
-
长剖有一个关键性质：每走一次短边，所在的长链长度至少 \(+1\)。
-
证明显然，否则长儿子应该是它。
-
由此可以证明到根至多走 \(O(\sqrt{n})\) 次短边，因为长链不交，且每次 \(+1\)，则 \(1\sim \sqrt{n}\) 就是极限了。某些奇怪的 dp 可能会用到这个性质。
-
树上 k 级祖先
-
考虑利用长剖的链长单调不降性，把某些询问拆成两半。
-
具体来讲，我们长剖，并记录每个长链从链头起向上/下走 \(1\sim len\) 步到哪里，\(len\) 为链长，\(O(n)\)。
-
然后倍增求一下所有点的 \(2^i\) 级祖先。\(O(n\log n)\)。
-
当询问时，我们首先向上跳到 \(highbit(k)\) 处，此时还需要跳 \(k-highbit(k)\leqslant \lfloor\dfrac{k}{2}\rfloor\) 步。证明如下：
-
若该跳跃没有改变所在的长链：\(len\geqslant highbit(k)\)，故用链头记录的向上走 \(1\sim len\) 的结果一定可以找到所要的祖先。
-
若该跳跃改变了所在的长链：
-
首先考察只走了一次短边的简单情况。此时找到短边的父节点发出的长边（这里按外向树考虑），比较两者终点向下延展出的长链（对，实边终点向回走的那部分不考虑），容易看出 \(len_{actual}\geqslant len_{visional}\)，否则短边才应当是长边。
-
推广到多次跳跃短边的情况，容易证明，最终所在的长链长度一定 \(\geqslant\) 跳过的距离。故，\(len\geqslant highbit(k)\geqslant k-highbit(k)\)，一定能用向上的走法一步走到。
-
-
同理，在链头下的也一定能走到。
-
-
综上，复杂度为 \(O(n\log n+q)\)。
长剖优化 DP
- 参见 长链剖分优化。