Level Ancestor 问题的若干解法

Level Ancestor 问题（以下简称“LA 问题”）的描述如下：

对于一棵有根树 $T$，给出树上的一个结点 $x$ 与一个整数 $k\leqslant depth(x)$，求出结点 $x$ 的第 $k$ 个祖先

最近学了一下这玩意儿，感觉挺神奇的，这篇文章就当学习笔记了。

算法一

可以考虑直接使用动态规划算法一次性预处理出所有答案并存在一张表里，基本的暴力算法。

预处理：$O(n^2)$，查询：$O(1)$

算法二

考虑对算法一进行优化，牺牲一部分查询的复杂度。

使用倍增的思想，对于每个结点预处理其到第 $1,2,4,\ldots,2^k$ 个祖先的跳转指针，这部分仍然可以通过动态规划算法完成。

查询时最坏情况下也只会跳转 $O(\lg n)$ 次。

预处理：$O(n\lg n)$，查询：$O(\lg n)$

算法三

让我们把算法二先放在一边，考虑使用最长路径分解。

我们将树中的一条最长路径从树中删去，原树将被划分成若干子树，接下来再对子树递归地进行上述操作，最后原树会被分解为若干条不相交路径。

这个分解过程可以被描述为一棵树，我们姑且称其为分解树。分解树中的每一个结点都对应原树的一条路径，我们只需要存储分解树中每个结点的父亲结点，以及每个结点对应路径的一端到另一端的所有原树结点即可。

于是对于 LA 问题的一次查询，当 $k$ 大于 $x$ 所处路径的长度时，我们可以通过分解树向上跳，否则答案必位于 $x$ 所处路径，可以直接查询。

显然在最坏情况下，我们的分解树会变成一条链，且结点对应路径长度分别为 $k,k-1,\ldots,2,1$，此时分解树树高是 $O(\sqrt n)$ 的。

预处理出每个结点的深度和高度，上述信息可以在 $O(n)$ 内处理完成。

预处理：$O(n)$，查询：$O(\sqrt n)$

算法四

考虑对算法三进行优化，使用梯子分解。

在最长路径分解的基础上，我们对每条路径额外存储其根节点在原树上的若干祖先，额外存储的祖先数等于该路径的长度。

对于 LA 问题的一次查询，我们发现 $x$ 所处的路径长度至少为 $x$ 在原树中的高度，于是向上跳转时我们可以利用额外存储的祖先（也即梯子分解中的梯子）来使得高度翻倍，于是最坏情况下的查询复杂度被我们降到了 $O(\lg n)$。预处理与算法三类似。

预处理：$O(n)$，查询：$O(\lg n)$

算法五

现在让我们把算法二和算法四结合起来。

对于 LA 问题的一次查询，我们先使用跳转指针跳最大的一步，此时答案的距离必定不超过刚刚跳的长度，即不超过当前位置的高度，于是我们可以通过额外存储的祖先立刻得到答案。

这就是 LA 问题的经典解法。

预处理：$O(n\lg n)$，查询：$O(1)$

算法六

考虑对算法五进一步优化。

查询的时间复杂度已经足够优秀了，我们考虑降低预处理的复杂度。预处理的瓶颈在于对于所有结点都存储了 $O(\lg n)$ 个到祖先的跳转指针。

我们发现要求一个结点的第 $k$ 级祖先，可以转换成求该结点所在路径的底端结点的第 $k'$ 级祖先，于是对于一条路径只需要存储最底端结点的 $O(\lg n)$ 个祖先即可。

对于整棵树，我们只预处理叶子结点的 $O(\lg n)$ 个祖先，预处理复杂度变为 $O(n+L\lg n)$，其中 $L$ 是叶子个数。对于一棵叶子个数为 $O(\frac{n}{\lg n})$ 的树，这个算法就可以达到 $O(n)$ 的预处理复杂度。

接下来我们考虑如何将任意树变为这样的一棵树。

剪枝（物理）

我们考虑将子树大小大于等于 $\frac14\lg n$ 的深度最大的结点的所有子结点从原树上剪下来，并记录其在原树上的父结点。接下来我们称原树剩下部分为宏观树，被剪去的部分为微观树。

此时宏观树叶子个数变为 $O(\frac{n}{\lg n})$，我们对宏观树使用上述提到的算法，在 $O(n)$ 时间内完成预处理。

接下来我们考虑对所有微观树使用算法一，由于大小为 $n$ 的本质不同的有根树的数量有一个 $2^{2n}$ 的上界（实则为卡特兰数），本质不同的微观树的数量不会超过 $2^{2(\frac14\lg n)}=\sqrt n$，因此对所有微观树预处理的复杂度为 $O(\sqrt n\lg^2n)$。

此时我们已经在 $O(n)$ 时间内完成预处理。对于每次查询，如果 $x$ 位于宏观树内，我们可以先找到其在宏观树上对应叶子并使用一次跳转指针和梯子得到答案，否则 $x$ 位于微观树内。我们考虑 $x$ 的第 $k$ 个祖先是否在宏观树内，如果是，则跳转到 $x$ 所在微观树对应的宏观树叶子上，以同样方式得到答案，否则直接查表。

至此，我们得到了一个花费 $O(n)$ 的空间，在 $O(n)$ 时间内预处理并 $O(1)$ 回答查询的静态树 LA 问题解法。