【板子】LCA Tarjan

这是一份基于 Tarjan塔扬算法的最近公共祖先LCA模板及详细讲解。该算法利用离线处理和并查集的思想是目前求解 LCA 问题最高效的算法之一时间复杂度 O(NQ)其中 N 为节点数Q 为询问数。1. 算法核心讲解核心思想离线 并查集Tarjan 算法是一种离线算法意味着你需要先读入所有的查询请求然后一次性处理完所有答案而不是像在线算法那样问一个答一个。它的巧妙之处在于利用了深度优先搜索DFS回溯时的信息结合并查集来维护当前的“祖先”关系。算法步骤解析初始化每个节点的父节点指向自己fa[i] i。标记所有节点未访问vis[i] false。深度优先搜索 (DFS)进入节点时标记当前节点u为已访问vis[u] true。递归子节点遍历u的所有子节点v。如果v未被访问则递归处理v并在回溯时将v的父节点指向u合并集合。处理查询关键步骤当从子节点回溯到当前节点u时检查所有以u为端点的查询(u, v)。如果节点v已经被访问过说明v所在的子树已经遍历完毕那么v当前的并查集根节点find(v)就是u和v的最近公共祖先LCA。为什么这样做是对的当 DFS 回溯到节点u时意味着u的子树已经全部遍历完成。此时所有在u子树中的节点它们的并查集都会指向u或者u的某个祖先。如果此时发现查询的另一个节点v已经被访问过说明v不在当前子树中那么它们的公共祖先只能是当前路径上深度较浅的那个节点也就是此时的并查集根节点。2. C 代码模板这是一个通用的 Tarjan LCA 模板支持多组查询。#include iostream #include vector #include cstring using namespace std; const int N 50010; // 节点最大数量 const int M 1000010; // 查询最大数量 // 存图邻接表 vectorint e[N]; // 存查询query[u] 中存储 pair查询的另一个点, 查询的ID vectorpairint, int query[N]; int fa[N]; // 并查集数组 bool vis[N]; // 访问标记数组 int ans[M]; // 存储查询结果ans[id] 表示第 id 个查询的答案 // --- 并查集模板 --- int find(int u) { if (u fa[u]) return u; return fa[u] find(fa[u]); // 路径压缩 } // --- Tarjan 算法核心 --- void tarjan(int u) { vis[u] true; // 1. 进入节点 u标记为已访问 // 2. 遍历所有邻接点子节点 for (auto v : e[u]) { if (!vis[v]) { tarjan(v); // 递归处理子树 fa[v] u; // 回溯时将子节点指向父节点合并集合 } } // 3. 处理所有以 u 为起点的查询 for (auto q : query[u]) { int v q.first; int id q.second; // 如果另一个节点 v 已经被访问过说明找到了 LCA if (vis[v]) { ans[id] find(v); // find(v) 即为 u 和 v 的最近公共祖先 } } } int main() { int n, m; // n 个节点m 个查询 cin n m; // 初始化并查集和访问标记 for (int i 1; i n; i) { fa[i] i; vis[i] false; } // 读入 n-1 条边 for (int i 1; i n; i) { int a, b; cin a b; e[a].push_back(b); e[b].push_back(a); } // 读入 m 个查询 for (int i 1; i m; i) { int a, b; cin a b; // 为了处理双向查询将 (b, i) 存入 a 的列表(a, i) 存入 b 的列表 query[a].push_back({b, i}); query[b].push_back({a, i}); } // 从根节点通常设为1开始跑 Tarjan tarjan(1); // 输出结果 for (int i 1; i m; i) { cout ans[i] endl; } return 0; }3. 复杂度分析时间复杂度DFS 遍历遍历整棵树复杂度为 O(N)。并查集操作每次find操作近似 O(1)路径压缩后。处理查询每个查询被处理两次存正反两个方向总复杂度为 O(Q)。总计O(NQ)。空间复杂度O(NQ)主要用于存储图、查询列表和并查集数组。4. 注意事项离线算法如果你需要实时获取某个查询的答案这个算法不适用应选择倍增法或树链剖分等在线算法。多组数据在竞赛中通常需要处理多组测试数据记得每次循环内重置数组特别是e[],query[],vis[]等。根节点选择代码中默认以节点1作为树的根节点开始 DFS这通常符合题目要求。