重链剖分

这里不详细讲解了。

P4219 [BJOI2014] 大融合

比较有用的 Trick：可以离线，倒叙做，然后转化成删边，用树剖做。

倒叙可以删除的时候上面的 $sz$ 全部减去下面的大小，下面的 $dep$ 全部减去上面的。

代码不想写了，写 LCT 吧。

就是按长度找出最长子树。

用长链剖分做这道题还是很奇妙啊，怎么想到的？

我们需要一个 $O(1)$ 的算法， $O(1)$ 有什么算法？打表，显然，我们不能打完，所以我们需要打我们需要的。

首先，我们需要一个 $Highbit$ 表示这个 $k$ 的二进制位的最高位（以下简写 $h$ ）。

我们第一步是从初始节点 $x$ 直接跳 $h$ 到达 $y$ ，然后我们就会发现，现在 $k-2^h<2^h<k$ 。

然后结合这个性质：

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

我们看到，这个 $y$ 的长链一定大于等于 $2^h$ ，所以也大于 $k-2^h$ 。

所以我们如果预处理出来每一条链向上和向下的点，是不是可以快速做出来呢？

即长链启发式合并。

这个和 dsu on tree 的不同就是按照子树深度来划分，主要维护带有深度的问题，然后是按照指针偏移来进行的转移。

老师说这个玩意儿完全不到 $10$ 级。

大概思路就是分治+去除冗余信息。

若询问至于部分节点形成的关键点有关，可以保留关键点集+他们的 LCA。

可以证明， $k$ 个点的 LCA（两两凑成的）最多有 $k-1$ 个，可以用哈夫曼树思想从深度最深的 LCA 合并来证明。