xxx 最小公共祖先（LCA）问题的Tarjan算法

题目描述
给定一棵有根树和若干查询，每个查询要求两个结点的最近公共祖先（LCA）。要求设计一个高效的离线算法，在一次深度优先搜索中处理所有查询。

解题过程

1. 问题分析

   • LCA问题要求找到树中两个结点在从根出发的路径上最深的公共祖先。
   • Tarjan算法通过并查集（Union-Find）和DFS实现离线处理，所有查询可在O(n + α(n))时间内解决（α是反阿克曼函数）。

2. 算法核心思想

   • 从根结点开始DFS，遍历子树时维护结点的祖先信息。
   • 利用并查集合并已访问的子树，使得当前结点能代表其所在集合的祖先。
   • 当处理完一个结点的所有子树后，检查与该结点相关的查询：若另一结点已被访问，其所在集合的祖先即为LCA。

3. 步骤详解
   步骤1：初始化

   • 为每个结点创建并查集，初始时每个结点的祖先为自己。
   • 标记所有结点为未访问状态。
   • 对每个查询(u, v)，将查询双向存储于u和v的查询列表中。

   步骤2：DFS遍历

   • 从根结点开始DFS，遍历结点u时：
     1. 标记u为已访问。
     2. 递归遍历u的所有子结点，遍历完成后将子结点所在集合与u合并（合并后集合的祖先设为u）。
     3. 遍历u的查询列表：若查询中的另一结点v已被访问，则LCA(u, v)为v当前所在集合的祖先。

   步骤3：并查集优化

   • 使用路径压缩和按秩合并，保证查询效率接近常数时间。

4. 示例演示
   树结构：根为1，子结点为2、3，2的子结点为4、5。
   查询：(4, 5)的LCA为2，(4, 3)的LCA为1。

   • DFS访问结点4：标记4为已访问，检查查询(4,5)中5未访问，暂不处理。回溯时合并4到2。
   • 访问结点5：标记5为已访问，检查查询(4,5)中4已访问，4的集合祖先为2，故LCA=2。回溯时合并5到2。
   • 访问结点3时，检查查询(4,3)：4已访问，4的集合祖先为1，故LCA=1。

5. 关键点

   • 离线算法需预先存储所有查询。
   • DFS回溯时合并集合，确保祖先信息正确。
   • 每个查询仅在两个结点均被访问时得到答案。

6. 应用场景

   • 树中路径问题（如最短路径计算）。
   • 网络路由中的公共祖先查找。

通过以上步骤，Tarjan算法以接近线性的时间复杂度高效解决LCA问题。