长链剖分

长链剖分选择深度最深的儿子为长儿子，并连接一条长边。除了长边都是轻边，由长边组成的链为长链。

长链剖分可以 \(O(1)\) 查询 \(k\) 级祖先，也可以优化深度相关的 dp。

查询 \(k\) 级祖先

对于一个节点 \(u\)，我们希望 \(O(1)\) 求出其的 \(k\) 级祖先 \(v\)。此时，可以使用长链剖分优化，步骤如下：

跳到 \(u\) 的 \(2^{\lfloor \log k\rfloor}\) 级祖先 \(v_1\)，记 \(V=\lfloor \log k\rfloor\)；
现在需要继续跳 \(k-2^V\) 步，即 \(v\) 和 \(v_1\) 的相对深度为 \(-(k-2^V)\)。
根据长链的性质，过 \(v_1\) 的长链的长度 \(len\) 满足 \(len\ge 2^V\ge k-2^V\)，说明 \(-(k-2^V)\in[-len,0]\) 同时长链链顶和 \(v_1\) 的相对深度在 \([-len,0]\) 之间，因此 \(v\) 和链顶的相对深度在 \([-len,len]\) 之间。
我们只需要预处理出链顶向下的 \(len\) 个儿子，以及向上的 \(len\) 个祖先，用 vector 存储，即可 \(O(1)\) 查询。

空间复杂度为 \(O(n\log n)\)，预处理时间复杂度为 \(O(n \log n)\)。

还没搞明白为什么不能用线段树合并代替。