Tarjan 的离线最近公共祖先（LCA）算法 题目描述 给定一棵有根树（节点数 \(n\)）和 \(m\) 个查询，每个查询询问两个节点 \(u\) 和 \(v\) 的最近公共祖先（LCA）。要求在线性时间内处理所有查询，即总时间复杂度为 \(O((n+m) \cdot \alpha(n))\)，其中 \(\alpha\) 是反阿克曼函数，可近似视为常数。 解题过程 1. 问题理解 最近公共祖先（LCA）指在树中，节点 \(u\) 和 \(v\) 的公共祖先中距离它们最近的节点。 离线算法指先读取所有查询，再一并处理，最后输出所有答案。 目标：利用并查集（Union-Find）和深度优先搜索（DFS）高效计算。 2. 算法核心思想 对树进行 DFS 遍历，同时维护一个并查集，用于记录节点的“集合代表”。 当 DFS 访问节点 \(u\) 结束时，将 \(u\) 合并到其父节点所在的集合。 在遍历过程中，若查询 \((u, v)\) 的另一个节点 \(v\) 已被访问，则 LCA 为 \(v\) 所在集合的代表（即当前集合的根）。 本质：利用 DFS 的递归特性，将 LCA 问题转化为节点合并与查询问题。 3. 具体步骤 步骤 1：数据预处理 输入树的 \(n-1\) 条边，建立邻接表。 输入 \(m\) 个查询 \((u, v)\)，对每个节点维护一个列表，存储与该节点相关的所有查询。 初始化并查集，每个节点单独为一个集合，祖先数组初始化为自身。 初始化访问标记数组 visited 为 false 。 步骤 2：DFS 遍历与并查集操作 从根节点开始 DFS。 对当前节点 \(u\) 的每个子节点 \(v\) 递归调用 DFS。 递归返回后，将 \(v\) 所在集合合并到 \(u\) 所在集合（ union(u, v) ），并令合并后集合的代表为 \(u\)。 标记 \(u\) 为已访问。 检查所有与 \(u\) 相关的查询：对每个查询 \((u, v)\)，如果 \(v\) 已被访问，则查询并查集中 \(v\) 所在集合的代表，该代表即为 LCA。 步骤 3：输出结果 在 DFS 过程中记录每个查询的答案。 DFS 结束后，按查询顺序输出所有 LCA。 4. 时间复杂度分析 DFS 遍历树：\(O(n)\)。 每个查询在常数时间内处理（并查集操作接近常数）。 总复杂度：\(O((n+m) \cdot \alpha(n))\)，近似为线性。 5. 示例演示 考虑一棵树（根为 1）： 边：1-2, 1-3, 2-4, 2-5 查询：(4,5), (4,3), (5,3) 执行过程： DFS 访问 4 并返回，将 4 合并到 2。 访问 5 时，查询 (4,5)：4 已访问，其集合代表为 2，LCA=2。 继续 DFS 合并，最终得到 LCA(4,3)=1, LCA(5,3)=1。 关键点 合并操作必须发生在子节点递归返回后，确保合并时当前集合代表是子树的最高祖先。 离线特性允许在 DFS 过程中即时回答查询。 这个算法结合了 DFS 的遍历顺序和并查集的高效合并，是解决批量 LCA 问题的经典方法。