xxx 最小公共祖先（LCA）问题的Tarjan算法 题目描述 给定一棵有根树（节点数为 \( n \)）和若干查询（每个查询包含两个节点 \( u \) 和 \( v \)），要求快速求出每对节点的最近公共祖先（LCA）。例如，若树为 1-2-3 （根为1），则 LCA(2,3)=2 。Tarjan算法通过离线处理（预先收集所有查询）和并查集（Union-Find）优化，在 \( O(n + q \alpha(n)) \) 时间内解决（\( q \) 为查询数，\( \alpha \) 为反阿克曼函数）。 解题步骤 预处理与初始化 存储树的邻接表结构，并记录根节点。 收集所有查询，为每个节点 u 维护一个查询列表，每个查询包含另一节点 v 和查询索引。 初始化并查集，每个节点初始父节点为自身，并标记为未访问。 深度优先搜索（DFS）遍历 从根节点开始DFS。遍历到节点 u 时，先递归处理其所有子节点。 关键思想：处理完子树后，将子树的并查集合并到当前节点 u ，保证子树中所有节点的代表元（并查集根）为 u 。 查询处理与并查集结合 当节点 u 的DFS完成时，标记 u 为已访问，并检查所有与 u 相关的查询 (u, v) 。 若 v 已被访问过，则查询 (u, v) 的LCA即为 v 在并查集中的当前代表元（因为 v 的子树尚未合并到其祖先，代表元即 v 所在子树的根，也就是LCA）。 使用并查集的“查找”操作快速获取代表元。 合并操作 递归回溯时，将当前节点 u 与父节点合并（通过并查集的“合并”操作），使父节点成为子树的新代表元。 示例演示 树：边为 (1,2) , (1,3) , (2,4) , (2,5) （根为1），查询 LCA(4,5) 和 LCA(4,3) 。 DFS到节点4：标记访问，查询 (4,5) 中5未访问，暂不处理；回溯到2时合并4到2。 DFS到节点5：标记访问，查询 (5,4) 发现4已访问，4的代表元为2，故 LCA(4,5)=2 。 DFS到节点3：标记访问，查询 (3,4) 中4已访问，4的代表元为1（因为2已合并到1），故 LCA(3,4)=1 。 关键点 离线算法：需预先知道所有查询，但效率高。 并查集优化路径压缩，使操作接近常数时间。 每个查询仅在两个节点均被访问时才可计算LCA。