LA 问题的若干种解法

看了眼 P5903 的题解区，方法还是挺多的，那我就浅浅的总结一下。

Algorithm 1

最简单的，直接往他的父亲节点跳，单次询问复杂度 \(\mathrm O(n)\)，总复杂度为 \(\mathrm O(qn)\)。这是最基础的写法。

Algorithm 2

我们用倍增的思想来做，这个也很简单不多讲，单次的复杂度为 \(\mathrm O(\log n)\)，总复杂度为 \(\mathrm O(q \log n)\)。

Algorithm 3

我们可以考虑使用重链剖分。如果这个链的顶端没有跳过的话，就直接跳到链顶的父亲，否则直接推就可以了，因为 \(dfs\) 序是连续的。单次复杂度也是 \(\mathrm O(\log n)\)，总复杂度为 \(\mathrm O(q \log n)\)。

看似复杂度是一样的，但是速度比 Algorithm 2 要快许多，此时已经可以通过了。

Algorithm 4

我们考虑如何优化 Algorithm 3。

我们发现我们需要跳到 \(k\) 级祖先的重链，然后我们就可以 \(\mathrm O(1)\) 知道祖先的位置了。然而跳链过程是 \(\mathrm O(\log n)\)，瓶颈就这这里。我们考虑如何更快地找到这条链。

我们发现一个点上面至多有 \(\log n\) 条链，那么我们直接二分这个点锁在的重链的位置即可。单次的复杂度为 \(\mathrm O(\log \log n)\)。由于瓶颈在前面了，所以总复杂度不变。

Algorithm 5

我们依然考虑如何优化 Algorithm 3。

我们可以一次跳 \(\sqrt \log n\) 个祖先，这样子我们就可以一次多跳几个祖先了。单次复杂度为 \(\mathrm O(\sqrt \log n)\)，总复杂度为 \(\mathrm O(q \sqrt \log n)\)。

Algorithm 6

这题的正解：长链剖分。

比较麻烦。先按照节点深度树剖。然后利用倍增数组跳到 \(2^x\)，剩余的距离差为 \(k_1\)，这里 \(2^x > k_1\)。然后由于长链的长度 \(> k_1\)，那么因此可以先将 \(x\) 跳到 \(x\) 所在链的顶点。

若之后剩下的级数为正，则利用向上的数组求出答案，否则利用向下的数组求出答案。单次时间复杂度 \(\mathrm O(1)\)，但是瓶颈在前面，复杂度为 \(\mathrm O(n \log n)\)。

Algorithm 7

这题还有一个比较科技的做法-----用 \(\pm 1 \ \text{FS(Find Smaller)}\) 问题。

我们发现 \(x\) 的深度为 \(d\) 的祖先是他后面的第一的深度 \(\le d\) 的节点。那么这个问题就是一个 \(\text{FS}\) 问题了。然后欧拉序具有 \(\pm 1\) 的性质。那么这个问题就变成了 \(\pm 1 \ \text{FS(Find Smaller)}\) 问题，这个问题有良好的性质。可以线性处理，在线常数查询。