LCA——最近公共祖先

LCA问题是指在一棵树中找到两个节点的最近公共祖先。最近公共祖先是指两个节点在树中的最近的共同祖先节点。例如，在下面这棵树中，节点$6$和节点7的最近公共祖先是节点$3$。

        1/   \2     3/ \   / \4   5 6   7

解决LCA问题的方法有很多种，下面介绍几种常见的方法。

树的深度优先搜索（DFS）算法
DFS算法可以遍历整棵树，并记录每个节点的父节点。当我们找到两个节点的路径时，我们可以比较路径中的节点，找到它们的最近公共祖先。

具体步骤如下：

从根节点开始，进行深度优先搜索，记录每个节点的父节点。
找到第一个节点的路径，记录路径上的所有节点。
找到第二个节点的路径，记录路径上的所有节点。
从两个路径的末尾开始，比较路径中的节点，直到找到它们的最近公共祖先。
这种方法的时间复杂度为$O(n)$，其中$n$是树中节点的数量。

树的Tarjan算法
Tarjan算法是一种基于并查集的算法，可以在一次遍历中找到多个节点的最近公共祖先。这种方法的时间复杂度为$O(n+q)$，其中$n$是树中节点的数量，$q$是查询的数量。

具体步骤如下：

从根节点开始，进行深度优先搜索，记录每个节点的父节点和祖先节点。
对于每个查询，使用并查集维护查询节点的祖先节点。
对于每个查询，从查询节点开始，向上遍历树，将遍历到的节点加入并查集中，直到找到一个已经在并查集中的节点，这个节点就是查询节点的最近公共祖先。
这种方法的优点是可以在一次遍历中处理多个查询，因此适用于查询数量较多的情况。

除了这些方法，还有其他一些解决LCA问题的算法，例如倍增算法、树链剖分算法等。具体使用哪种方法取决于树的结构和问题的要求。

树上倍增（Tree Upward Doubling）是一种解决最近公共祖先（LCA）问题的常用算法之一。它利用了树的特性，通过预处理和查询操作来找到两个节点的最近公共祖先。

树上倍增算法的核心思想是将每个节点的跳跃步长翻倍，以便在查询时能够快速跳到更高层的祖先节点。具体步骤如下：

预处理阶段：

对于每个节点，计算它的$2^i$级祖先（其中$i$从$0$开始递增）。
使用深度优先搜索（DFS）遍历树，记录每个节点的深度和父节点。
对于每个节点$v$，计算$v$的第$2^i$级祖先为$v$的父节点的第$2^{(}$${}^i$${}^{-}$${}^1$${}^{)}$级祖先。
查询阶段：

对于给定的两个节点$u$和$v$，假设深度$(u)$ > 深度$(v)$。
从深度$(u)$开始，通过不断将$u$跳到更高层的祖先节点，直到深度$(u)$ = 深度$(v)$。
在每一步跳跃中，将u跳到它的第$2^i$级祖先，其中i是满足深度$(u)-2^i\ge$ 深度$(v)$的最大值。
如果$u=v$，说明已经找到了最近公共祖先。
否则，同时将$u$和$v$跳到它们的第$2^i$级祖先，继续进行下一步跳跃。
重复上述步骤，直到$u$和$v$的父节点相同，这个父节点就是它们的最近公共祖先。
树上倍增算法的时间复杂度为$O(nlog(n))$的预处理时间和$O(log(n))$的查询时间，其中$n$是树中节点的数量。这使得它在处理多次查询的情况下非常高效。