长链剖分

长链剖分

考虑将重儿子设为链最长的那一个，剖分是简单的，可以做到 $\Theta(n).$

这样剖分有一些性质：

• 链长和是 $n$，因为每个点都在且仅在一条链中。

• 任意点 $x$ 的 $k$ 级祖先 $y$ 到它所在的长链底端距离不小于 $k$ 。因为如果 $x$ 和 $y$ 在同一条长链上，那么 $y$ 所在的长链长度不小于 $k$ 。如果它们不在同一条的长链上，那么 $y$ 到另一条长链底端的距离一定大于 $k$，否则的话 $x$ 所在的链就可以接在 $y$ 上成为更长的链。

• 从任意一个点开始跳重链的次数最多是 $\sqrt{n}$ 级别的。因为容易知道每次跳到的长链长度一定大于当前链，于是最坏情况是分别经过了长度为 $1, 2, 3, \cdots, \sqrt{n}$ 的长链，最多跳 $\sqrt{n}$ 次。

$\Theta(n \log n) - \Theta(1)$ 算 $k$ 级祖先

考虑预处理每个点的 $2$ 的幂次级祖先，对于一次询问 $(u, k)$，首先跳到 $u$ 的 $highbit(k)$ 级祖先 $v$ 上，由长链剖分的性质可知，$v$ 到其所在长链底端的距离不小于 $highbit(k).$

由于长链长度之和为 $n$，所以我们可以预处理每条链顶端节点的 $l$ 级祖先，$l$ 取遍不大于链长的所有整数。并且我们还可以存下每条链的所有节点，挂在链顶。

这样，对于一次询问，假设 $v$ 的 $k - higtbit(k)$ 级祖先不超过链顶，那么可以直接查询，否则也可以从链顶跳若干步得到。由于 $k - highbit(k) < hightbit(k)$，故其一定小于链长，要查询的祖先是预处理过的。

时间复杂度 $\Theta(n \log n)$ 预处理，单次查询 $\Theta(1)$。