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

题目描述
给定一棵有根树和若干查询，每个查询要求两个节点的最近公共祖先（LCA）。例如，对于树：

        1
       / \
      2   3
     / \   \
    4   5   6

查询 (4,5) 的 LCA 是 2，查询 (4,6) 的 LCA 是 1。要求高效处理多个查询。

解题过程
Tarjan 算法通过一次深度优先搜索（DFS）处理所有查询，利用并查集（Union-Find）记录节点关系，实现离线查询（所有查询已知）。

步骤详解

1. 初始化

   • 为每个节点创建集合，初始时每个节点独立一个集合。
   • 记录每个节点的祖先：初始时祖先为自身。
   • 记录访问状态：所有节点初始未访问。

2. DFS 遍历树

   • 从根节点开始 DFS。访问节点 u 时：
     a. 标记 u 为已访问。
     b. 递归处理 u 的所有子节点。处理完子节点后，将子节点所在集合与 u 合并，并设置 u 为合并后集合的代表（祖先）。

3. 处理查询

   • 当节点 u 的子树遍历完成后，检查所有与 u 相关的查询 (u, v)。
   • 若 v 已被访问，则查询 (u, v) 的 LCA 为 v 当前所在集合的祖先。
   • 由于 DFS 特性，当 v 已被访问时，v 所在集合的祖先即为 u 和 v 的 LCA。

4. 并查集优化

   • 使用路径压缩和按秩合并优化并查集操作，使每次操作接近常数时间。

示例演示
对上述树和查询 (4,5), (4,6)：

• DFS 访问节点 4：标记访问，无子节点。处理查询 (4,5)：5 未访问，暂不处理。
• 回溯到节点 2：先处理子节点 5。访问 5 后，合并 {4} 和 {5} 到集合 {2}，祖先设为 2。
• 在节点 2 处理查询 (4,5)：5 已访问，LCA 为 5 的集合祖先 2。
• 继续 DFS 至节点 6，回溯到 3 和 1。在节点 1 处理查询 (4,6)：6 已访问，LCA 为 6 的集合祖先 1。

复杂度分析

• 时间复杂度：O(n + α(n)Q)，其中 n 为节点数，Q 为查询数，α 为反阿克曼函数。
• 空间复杂度：O(n) 存储树和查询。

关键点

• 利用 DFS 遍历顺序和并查集动态维护集合，确保查询时能快速确定 LCA。
• 离线算法需预先知道所有查询，适合批量处理场景。