【题解】Ynoi2007 rfplca / CF1491H Yuezheng Ling and Dynamic Tree 分块 — Qiuly

这一类题带有鲜明的套路：分块，然后将跳大块和跳小块分开计算复杂度，跳大块最多跳 $B$ 次，小块最多暴力更新 $\frac{n}{B}$ 次。

同样考虑维护 $b_i$ 表示 $i$ 第一次跳出所在块会跳到哪里去，那么查询的话就可以两个点往前跳，跳到同一个大块后再继续不断跳 $b_i$ 直到相等，撤回来跳 $a_i$ 即可，单次是 $B+\frac{n}{B}$ 的。

问题在于怎么求 $b_i$，注意到所有点都跳出去后就可以打标记了，如果一个块内还有祖先每跳出块的就暴力重构，一个块被重构的次数是 $O(\frac{n^2}{B^2})$ 的。

取 $B=\sqrt{n}$，时间复杂度为 $O(n\sqrt{n})$ 。

代码：Submission #128873501 – Codeforces