1. 项目概述从“最近公共祖先”到算法竞赛的基石最近公共祖先简称LCA这个概念听起来有点学术但它在解决很多实际问题时就像一把万能钥匙。想象一下你有一棵庞大的家族树想知道两个远房亲戚在哪个老祖宗那里第一次“分家”这个老祖宗就是他们的最近公共祖先。在计算机的世界里这棵树变成了程序里的数据结构而LCA算法就是快速定位这个“分叉点”的工具。无论是社交网络里计算两个人的最短关系链还是文件系统里寻找两个目录的最近共同父文件夹甚至是编译器优化中分析数据依赖关系LCA都扮演着核心角色。尤其在算法竞赛和面试中它几乎是图论和树上问题的“标配”考点。我最初接触LCA时觉得它就是个简单的概念直到在解决一道看似复杂的树上路径查询问题时碰壁才意识到高效求解LCA是解开一系列难题的关键。网上资料虽多但往往只讲单一方法缺乏横向对比和实战细节。这次我将结合自己踩过的坑和实战经验系统梳理四种最主流、最实用的LCA求解模板倍增法、Tarjan离线算法、树链剖分法以及基于RMQ的ST表法。每种方法都有其独特的思维角度和适用场景我会带你不仅看懂模板代码更要理解背后的设计逻辑、时间复杂度的权衡以及在实际编码中如何避开那些教科书上不会写的“坑”。无论你是正在备赛的选手还是希望深化数据结构理解的开发者这篇从原理到实战的详解都能让你对LCA有一个透彻的掌握。2. 核心思路与算法选型四种方法的哲学面对一棵树和若干次查询求两个节点的LCA最笨的办法就是沿着父节点一步一步往上爬直到相遇。当树退化成一条链时这种“爬楼梯”的方法复杂度会退化到O(N) per query在大量查询面前不堪一击。因此所有高效的LCA算法核心目标都是加速这个“向上跳跃”的过程或者改变问题模型用预处理的空间换取查询时的时间。2.1 倍增法稳健的“二进制跳跃”这是我最推荐新手首先掌握的方法因为它思想直观编码相对固定且在线查询即每次查询独立处理的特性使其适用性极广。核心思想预处理每个节点向上跳 2^k 步所能到达的祖先节点。查询时不再是一步一步爬而是尝试以2的幂次如16, 8, 4, 2, 1为步长进行跳跃快速将两个节点调整到同一深度然后再一起向上跳找到LCA。为什么是2的幂次因为任何整数都可以用二进制表示。通过预处理2^k级祖先我们可以在O(logN)的时间内组合出任意步数的跳跃。这本质上是二进制拆分思想在树上的应用。选型考量优点在线算法无需预先知道所有查询思路清晰模板化程度高时间复杂度均衡预处理O(NlogN)查询O(logN)。缺点相比其他方法查询的logN因子在极端高频查询下可能成为瓶颈需要O(NlogN)的额外存储空间记录祖先信息。适用场景通用性强尤其适合查询并非一次性给出的动态场景如交互式问题或查询依赖前序结果的场景。2.2 Tarjan离线算法巧妙的“并查集与DFS”Tarjan算法展现了“离线处理”和“并查集”结合的魅力。它通过一次深度优先遍历就能回答所有预先知道的查询。核心思想算法在DFS遍历树的过程中将已访问完毕且回溯的子树“合并”到其当前父节点下使用并查集。当遍历到某个查询节点u时如果另一个节点v已经被访问过那么v所在集合的代表元并查集的根就是u和v的LCA。可以想象成在遍历过程中不断将已经摸清的“领地”合并并随时回答涉及已探索领地的询问。为什么用并查集并查集完美地维护了“已访问完毕的子树集合”并且可以快速找到这个集合的最高代表即当前子树的根也就是LCA候选。选型考量优点时间复杂度极优预处理O(NQα(N))近乎线性思想巧妙体现了离线处理的威力。缺点必须是离线算法需要提前知道所有查询递归DFS实现可能带来栈溢出风险对于深度很大的树需手动模拟栈理解和实现比倍增法稍复杂。适用场景所有查询一次性给出的静态场景且对效率要求极高。这是很多竞赛题的标准解法。2.3 树链剖分法重链上的“高速公路”树链剖分本身是一种将树“拍平”到线段树等数据结构上进行维护的强大技术。用它来求LCA可以看作是其一个“副产品”但效率非常高。核心思想通过两次DFS将树划分成若干条“重链”由重儿子连续连接形成的链。每个节点都记录所在重链的顶端节点。求LCA时比较两个节点所在重链的顶端将顶端深度较大的节点快速上提到其顶端节点的父节点处如此反复直到两个节点处于同一条重链上此时深度较小的节点就是LCA。为什么快重链剖分保证了从任意节点到根节点的路径上最多只会经过O(logN)条不同的重链。每次跳跃都是直接从当前节点跳到链顶跳过了链上所有节点从而将路径长度压缩到对数级别。选型考量优点查询复杂度也是O(logN)但常数通常比倍增法小树剖本身是非常有用的数据结构学会后可以解决一大类树上路径修改/查询问题。缺点预处理过程比倍增法复杂需要两次DFS代码量相对较大如果仅仅为了求LCA而学习树剖学习成本较高。适用场景当问题不仅仅是求LCA还涉及树上路径的权值修改、查询等操作时树链剖分是集成度更高的解决方案。2.4 RMQST表法转化为区间最值问题这种方法提供了一个全新的视角将LCA问题转化为序列上的RMQ区间最小值问题。核心思想对树进行欧拉序遍历DFS每次访问节点都记录得到一个长度为2N-1的序列。同时记录每个节点在欧拉序中第一次出现的位置。关键结论是两个节点的LCA等于它们第一次出现位置所构成的区间内深度最小的那个节点。这样我们只需要用一个支持O(1)查询的RMQ数据结构如ST表来维护欧拉序列中节点的深度即可实现O(1)的LCA查询。为什么是欧拉序欧拉序完整地记录了DFS的访问轨迹保证了任意两节点间的路径上的所有节点都会出现在它们第一次出现的位置之间的序列段中并且LCA恰好是其中深度最小的。选型考量优点查询速度最快达到O(1)适合海量查询ST表的构建思想也很经典。缺点预处理复杂度O(NlogN)且空间消耗较大存储欧拉序和ST表纯粹的查询算法不支持在线动态处理其他树上操作。适用场景适用于查询次数巨大Q远大于N且查询是离线的静态场景。在一些对查询时间极端苛刻的题目中会是首选。实操心得方法选择速查面对一道题如何快速选择查询是否离线是 - 优先考虑Tarjan理论最优或RMQ查询最多。查询是否在线或动态是 - 选择倍增或树链剖分。是否涉及路径上的其他操作如修改、求和是 -树链剖分是更全面的选择。是否只是单纯海量LCA查询是 -RMQST表可能最快。追求编码速度和稳妥-倍增法是万金油首选。3. 算法细节解析与模板实现理解了宏观思路我们来深入每种方法的实现细节并给出可直接使用的模板代码。我会用C作为示例语言并附上关键注释。3.1 倍增法模板详解倍增法的实现分为两大步预处理和查询。预处理阶段 目标是计算出fa[u][k]数组表示节点u向上跳2^k步后到达的祖先节点。通常设fa[u][0]为u的直接父节点。const int MAXN 100005; // 最大节点数 const int LOG 17; // 2^LOG MAXN 通常取17或20足够 vectorint tree[MAXN]; // 树的邻接表 int depth[MAXN]; // 节点深度 int fa[MAXN][LOG]; // 倍增祖先数组 // DFS预处理 depth 和 fa[u][0] void dfs(int u, int p) { // u当前节点 p父节点 fa[u][0] p; depth[u] depth[p] 1; for (int i 1; i LOG; i) { // 核心递推u的2^i祖先 (u的2^(i-1)祖先)的2^(i-1)祖先 fa[u][i] fa[fa[u][i-1]][i-1]; if (fa[u][i] 0) break; // 如果已经跳到根以上可以提前终止 } for (int v : tree[u]) { if (v p) continue; dfs(v, u); } }查询阶段 给定节点a和b求它们的LCA。对齐深度将深度较大的节点向上跳直到与另一个节点深度相同。跳跃时从大步长2^(LOG-1)开始尝试。同步上跳如果此时两个节点相同则它就是LCA一个节点是另一个的祖先。否则让它们一起向上跳从大步长开始尝试目标是跳到LCA的直接子节点。最后这两个节点的父节点就是LCA。int lca(int a, int b) { // 1. 确保a是深度较大的节点方便处理 if (depth[a] depth[b]) swap(a, b); // 2. 将a跳到与b同深度的位置 int diff depth[a] - depth[b]; for (int i 0; diff 0; i) { if (diff 1) { // 利用二进制位判断是否需要跳2^i步 a fa[a][i]; } diff 1; } // 更清晰的写法 // for (int i LOG-1; i 0; --i) { // if (depth[fa[a][i]] depth[b]) { // 如果跳了还在b下面或同层就跳 // a fa[a][i]; // } // } // if (a b) return a; // 处理b是a祖先的情况 // 3. 如果此时已经相同直接返回 if (a b) return a; // 4. a和b一起向上跳目标是LCA的直接子节点 for (int i LOG-1; i 0; --i) { // 如果跳了之后不相同说明还没到LCA可以跳 if (fa[a][i] ! fa[b][i]) { a fa[a][i]; b fa[b][i]; } } // 循环结束后a和b的父节点就是LCA return fa[a][0]; }注意事项LOG大小的选择LOG值应满足2^LOG N。通常N1e5时取17N1e6时取20即可。根节点的处理通常将根节点的父节点设为0depth[0] 0fa[root][0]0。这样在跳跃时跳到0节点是安全的表示跳出树了。递推顺序预处理DFS必须是先计算完当前节点的fa[u][i]再递归子节点确保子节点递推时父节点的信息已就绪。查询时的跳跃顺序务必从大到小尝试步长i从LOG-1递减到0这样才能像二进制拆分一样组合出任意步数。3.2 Tarjan离线算法模板详解Tarjan算法需要预先存储所有查询。我们使用并查集DSU来维护已访问节点的集合。const int MAXN 100005; const int MAXQ 100005; // 最大查询数 vectorint tree[MAXN]; vectorpairint, int queries[MAXN]; // queries[u] {v, query_id} int ans[MAXQ]; // 存储每个查询的答案 int parent[MAXN]; // 并查集父节点 int vis[MAXN]; // 标记节点状态0未访问1访问中2已访问并合并 // 简易并查集 int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int x, int y) { // 这里y是x的父节点简单合并即可 parent[find(x)] find(y); } void tarjan(int u) { vis[u] 1; // 标记为正在访问 for (int v : tree[u]) { if (vis[v]) continue; tarjan(v); unite(v, u); // 关键子节点v访问完毕将其集合合并到当前节点u // 此时以u为根的子树已全部访问并合并到u的集合下 } vis[u] 2; // 标记为已访问完毕 // 处理所有与u相关的查询 for (auto [v, id] : queries[u]) { if (vis[v] 2) { // 如果另一个节点v也已经访问完毕 ans[id] find(v); // 那么v所在集合的代表元就是LCA } } } // 主函数调用前准备 int main() { // ... 读入树 ... // ... 读入Q个查询 (a, b)并构建queries数组: queries[a].push_back({b, i}); queries[b].push_back({a, i}); for (int i 1; i N; i) parent[i] i; // 初始化并查集 tarjan(root); // 从根开始DFS // 输出 ans[0...Q-1] }注意事项查询的存储每个查询(a,b)需要双向存储到queries[a]和queries[b]中因为DFS过程中先访问到a或b是不确定的。合并时机一定要在递归子节点之后处理当前节点查询之前进行合并unite(v, u)。这保证了当处理u的查询时以u为根的子树已经合并到了u下但u本身还没有合并到它的父节点下因此find(v)返回的正好是u和v的LCA。状态标记vis[u]2表示u的所有子树都已处理完毕。只有另一个节点状态为2时才能确定其所在集合的代表元是LCA。栈溢出对于深度可能很大的树如链递归DFS可能导致栈溢出。可以使用显式栈进行迭代遍历但实现会复杂不少。3.3 树链剖分法模板详解树链剖分求LCA是其核心应用之一。我们需要预处理出以下信息son[u]: u的重儿子sz[u]: 以u为根的子树大小top[u]: u所在重链的顶端节点fa[u]: u的父节点dep[u]: u的深度const int MAXN 100005; vectorint tree[MAXN]; int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN]; int top[MAXN]; // 第一遍DFS求fa, dep, sz, son void dfs1(int u, int p) { fa[u] p; dep[u] dep[p] 1; sz[u] 1; son[u] -1; int maxSize 0; for (int v : tree[u]) { if (v p) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] maxSize) { maxSize sz[v]; son[u] v; } } } // 第二遍DFS求top连接重链 void dfs2(int u, int tp) { top[u] tp; if (son[u] ! -1) { dfs2(son[u], tp); // 重儿子继承当前链的顶端 } for (int v : tree[u]) { if (v fa[u] || v son[u]) continue; dfs2(v, v); // 轻儿子自己作为新链的顶端 } } // 树剖LCA查询 int lca(int a, int b) { while (top[a] ! top[b]) { // 当不在同一条重链上时 if (dep[top[a]] dep[top[b]]) swap(a, b); // 将深度较大的链顶节点向上跳 a fa[top[a]]; } // 此时a和b在同一条重链上深度较小的就是LCA return dep[a] dep[b] ? a : b; } // 初始化 void init(int root) { dfs1(root, 0); dfs2(root, root); }注意事项两遍DFSdfs1计算基本信息并确定重儿子dfs2进行重链剖分。顺序不能错。重儿子的定义子树大小最大的儿子。如果子树大小相同任选一个即可。top数组的赋值重儿子的top继承自父节点轻儿子的top是自己。这保证了重链的连续性。LCA查询逻辑核心是不断比较链顶深度将深度大的节点跳到其链顶的父节点。这个过程直到两者链顶相同。由于重链数量是O(logN)所以跳跃次数也是O(logN)。与倍增法对比树剖的logN常数通常更小因为它是基于树的重链性质而倍增是基于二进制。3.4 RMQST表法模板详解这种方法将树转化为欧拉序列并用ST表维护深度最小值。const int MAXN 100005; const int LOG 17; // 2^LOG 2*MAXN vectorint tree[MAXN]; int dep[MAXN]; int euler[2 * MAXN]; // 欧拉序列 int first[MAXN]; // 节点在欧拉序中首次出现的位置 int st[2 * MAXN][LOG]; // ST表存储欧拉序下标 int lg2[2 * MAXN]; // 预处理log2值 int idx 0; // 欧拉序索引 // DFS生成欧拉序和first数组 void dfs(int u, int p) { dep[u] dep[p] 1; first[u] idx; euler[idx] u; for (int v : tree[u]) { if (v p) continue; dfs(v, u); euler[idx] u; // 回溯时再次记录u } } // 预处理ST表维护的是深度最小的节点在欧拉序中的下标 void buildST() { int n idx; // 欧拉序列长度 // 预处理对数表 lg2[1] 0; for (int i 2; i n; i) lg2[i] lg2[i / 2] 1; // 初始化ST表st[i][0] i for (int i 0; i n; i) st[i][0] i; for (int j 1; (1 j) n; j) { for (int i 0; i (1 j) - 1 n; i) { int a st[i][j - 1]; int b st[i (1 (j - 1))][j - 1]; // 比较的是节点深度而非下标本身 st[i][j] (dep[euler[a]] dep[euler[b]]) ? a : b; } } } // RMQ查询返回欧拉序中[l, r]区间内深度最小节点的下标 int queryST(int l, int r) { int k lg2[r - l 1]; int a st[l][k]; int b st[r - (1 k) 1][k]; return (dep[euler[a]] dep[euler[b]]) ? a : b; } // LCA查询 int lca(int a, int b) { int l first[a], r first[b]; if (l r) swap(l, r); int pos queryST(l, r); // 得到深度最小节点的下标 return euler[pos]; // 返回该节点 } // 初始化 void init(int root) { dep[0] -1; // 方便根节点深度为0 dfs(root, 0); buildST(); }注意事项欧拉序列长度是2*N-1数组要开足够大。first数组记录每个节点第一次出现的位置这是查询区间的依据。ST表存储内容ST表st[i][j]存储的是区间[i, i2^j-1]内深度最小的节点在欧拉序euler中的下标而不是节点编号本身。比较时比较的是dep[euler[下标]]。查询区间LCA(a,b) 对应的RMQ区间是[first[a], first[b]]需保证左小右大。这个区间包含了从第一次访问a到第一次访问b之间DFS遍历的所有节点LCA的深度一定是其中最小的之一。空间与时间预处理O(NlogN)空间O(NlogN)查询O(1)。当N很大时logN倍的常数和空间消耗需要考虑。4. 实战对比与性能分析纸上得来终觉浅我们通过一个具体的例子来感受四种方法的差异。假设有一棵N10^5个节点的树Q10^6次查询。特性倍增法Tarjan离线法树链剖分法RMQST表法预处理时间O(N log N)O(N α(N))O(N)O(N log N)单次查询时间O(log N)O(α(N)) (近乎O(1))O(log N)O(1)总查询时间O(Q log N)O(NQ)O(Q log N)O(Q)空间复杂度O(N log N)O(NQ)O(N)O(N log N)算法类型在线离线在线离线编码复杂度简单中等中等偏难中等额外功能可求k级祖先仅LCA支持路径操作仅LCA适用场景通用动态查询静态大量查询需路径操作超大量静态查询分析Tarjan在静态查询下总时间最优但必须离线。RMQ查询最快但预处理和空间开销大也必须离线。倍增法是平衡的选择在线且编码简单是很多人的首选模板。树链剖分的查询常数小且功能强大是解决综合性问题的利器。实操心得性能测试中的坑常数问题时间复杂度的大O记号忽略了常数。例如树剖的logN常数通常小于倍增法。在N和Q都达到百万级别时这个差异会很明显。缓存友好性倍增法的fa[][]数组访问是跳跃的可能造成缓存命中率低。而树剖的top[],fa[]访问相对连续。在极端优化时需要考虑。递归开销Tarjan和DFS预处理如果递归太深需要改为迭代栈否则会Runtime Error栈溢出。内存限制RMQ法的ST表是O(N log N)的当N很大如1e6时st[2N][LOG]可能超过内存限制~2e6204B ≈ 160MB。需要权衡。5. 常见问题与调试技巧在实际编码和解题中会遇到一些典型问题。这里记录了我踩过的坑和解决方法。5.1 倍增法常见问题问题1查询结果错误经常返回0或错误节点。检查点1预处理DFS的递归基。确保根节点的fa[root][0] 0或-1等标识并且在递推fa[u][i] fa[fa[u][i-1]][i-1]时当fa[u][i-1]为0时fa[u][i]也应设为0避免访问非法内存。检查点2深度对齐的逻辑。确保在将深度大的节点a向上跳时判断条件是if (depth[fa[a][i]] depth[b])而不是if (fa[a][i] ! 0)。前者能正确处理b是a祖先的情况。检查点3同步上跳的循环。必须是for (int i LOG-1; i 0; --i)从大到小。并且判断条件是if (fa[a][i] ! fa[b][i])这保证了最后停在LCA的子节点。问题2程序在大型数据下超时。优化点1减少LOG大小。根据N精确计算所需的LOGLOG ceil(log2(N)) 1。优化点2使用链式前向星存图。如果树非常稠密边数多vectorint tree[MAXN]可能效率不如链式前向星。优化点3输入输出优化。使用scanf/printf或关闭同步的cin/cout。5.2 Tarjan算法常见问题问题答案部分正确部分错误。检查点1查询的存储。是否对每个查询(a,b)在queries[a]和queries[b]中都添加了ID是否对应正确检查点2并查集合并顺序。必须在tarjan(v)递归之后处理当前节点查询之前进行unite(v, u)。这个顺序是算法的核心。检查点3状态判断。只有当另一个节点vis[v] 2已访问完毕时find(v)的结果才是LCA。如果写成vis[v] 1得到的结果可能是错误的。检查点4并查集路径压缩。find函数中一定要有路径压缩parent[x] find(parent[x])否则复杂度会退化。5.3 树链剖分常见问题问题LCA查询陷入死循环或结果错误。检查点1dfs1中son[u]的初始化。如果没有重儿子应初始化为-1或0并在dfs2中做好判断。检查点2dfs2中重链的连接。重儿子调用dfs2(son[u], tp)继承链头轻儿子调用dfs2(v, v)自己作为新链头。检查点3LCA查询循环条件。while (top[a] ! top[b])内部比较的是dep[top[a]]和dep[top[b]]将深度大的链头节点a上提a fa[top[a]]。检查点4根的父节点设置。通常将根的父节点设为0且dep[0] 0。5.4 RMQ法常见问题问题查询返回的节点不是LCA。检查点1欧拉序生成。DFS回溯时是否再次记录了当前节点ueuler[idx] u;这句必须在递归子节点之后。检查点2first数组记录的是第一次出现的位置。在DFS第一次访问节点u时记录first[u] idx。检查点3ST表比较的是深度。st[i][j]存储的是最小深度节点的下标。在queryST和buildST中比较的是dep[euler[a]]和dep[euler[b]]而不是a和b。检查点4查询区间。l first[a],r first[b]务必保证l r。5.5 通用调试技巧小数据画图模拟用一棵5-6个节点的小树手工模拟算法的每一步尤其是数组值的变化与程序输出对比。这是最有效的定位逻辑错误的方法。打印关键数组在调试时打印出fa[][]倍增、parent[]Tarjan、top[]/son[]树剖、euler[]/first[]RMQ等数组检查是否符合预期。对拍写一个暴力求LCA的算法DFS向上爬用随机生成的大树和大量查询对比四种高效算法的结果是否与暴力结果一致。这是检验正确性的终极手段。边界测试测试LCA是根节点的情况、两个节点相同的情况、一个节点是另一个节点祖先的情况。6. 模板选择与扩展应用指南经过上面的详细拆解你应该对四种方法有了深入的理解。最后我分享一下在实际项目中如何选择和扩展这些模板。如何选择记住这个流程看查询是否离线离线 - Tarjan或RMQ在线 - 倍增或树剖。看功能需求只需LCA - 排除树剖除非学过了可能需要路径查询/修改 - 优先树剖。看数据规模N, Q 1e5四种方法均可选你最熟悉的。Q 极大 (1e6以上)离线RMQ法O(1)查询优势巨大。N 极大 (1e6以上)在线倍增法要小心LOG和空间树剖的常数可能更优。看个人熟练度比赛时优先使用你最熟悉、最不容易写错的方法。稳定输出比追求最优复杂度更重要。对于大多数人倍增法是这个角色。扩展应用倍增法很容易扩展来求树上两点的路径长度dist depth[a] depth[b] - 2*depth[lca]或者求一个节点的第k个祖先k级祖先问题。树链剖分其威力远不止LCA。结合线段树可以高效处理树上路径的权值修改、查询以及子树修改、查询。这是它最大的优势。Tarjan/RMQ它们是非常经典的离线算法和数据结构其思想可以迁移到其他问题上。例如Tarjan算法还可以用于求强连通分量、割点、桥等。我个人在竞赛和工程中的习惯是默认使用倍增法作为我的LCA模板因为它足够通用和可靠。只有当题目明确要求离线处理且查询量巨大时我会转向RMQ法。而如果题目涉及复杂的路径操作树链剖分则是必须祭出的武器。至于Tarjan它更像一个优美的理论解法在只需要LCA且离线的场景下它能提供最优雅的复杂度。理解这四种方法不仅仅是学会了四个模板更是掌握了四种重要的算法思想二进制倍增、离线处理与并查集结合、树链划分与路径压缩、以及将树问题转化为序列RMQ问题。这些思想会在你解决更多复杂问题时提供宝贵的思路。
1. 项目概述从“最近公共祖先”到算法竞赛的基石最近公共祖先简称LCA这个概念听起来有点学术但它在解决很多实际问题时就像一把万能钥匙。想象一下你有一棵庞大的家族树想知道两个远房亲戚在哪个老祖宗那里第一次“分家”这个老祖宗就是他们的最近公共祖先。在计算机的世界里这棵树变成了程序里的数据结构而LCA算法就是快速定位这个“分叉点”的工具。无论是社交网络里计算两个人的最短关系链还是文件系统里寻找两个目录的最近共同父文件夹甚至是编译器优化中分析数据依赖关系LCA都扮演着核心角色。尤其在算法竞赛和面试中它几乎是图论和树上问题的“标配”考点。我最初接触LCA时觉得它就是个简单的概念直到在解决一道看似复杂的树上路径查询问题时碰壁才意识到高效求解LCA是解开一系列难题的关键。网上资料虽多但往往只讲单一方法缺乏横向对比和实战细节。这次我将结合自己踩过的坑和实战经验系统梳理四种最主流、最实用的LCA求解模板倍增法、Tarjan离线算法、树链剖分法以及基于RMQ的ST表法。每种方法都有其独特的思维角度和适用场景我会带你不仅看懂模板代码更要理解背后的设计逻辑、时间复杂度的权衡以及在实际编码中如何避开那些教科书上不会写的“坑”。无论你是正在备赛的选手还是希望深化数据结构理解的开发者这篇从原理到实战的详解都能让你对LCA有一个透彻的掌握。2. 核心思路与算法选型四种方法的哲学面对一棵树和若干次查询求两个节点的LCA最笨的办法就是沿着父节点一步一步往上爬直到相遇。当树退化成一条链时这种“爬楼梯”的方法复杂度会退化到O(N) per query在大量查询面前不堪一击。因此所有高效的LCA算法核心目标都是加速这个“向上跳跃”的过程或者改变问题模型用预处理的空间换取查询时的时间。2.1 倍增法稳健的“二进制跳跃”这是我最推荐新手首先掌握的方法因为它思想直观编码相对固定且在线查询即每次查询独立处理的特性使其适用性极广。核心思想预处理每个节点向上跳 2^k 步所能到达的祖先节点。查询时不再是一步一步爬而是尝试以2的幂次如16, 8, 4, 2, 1为步长进行跳跃快速将两个节点调整到同一深度然后再一起向上跳找到LCA。为什么是2的幂次因为任何整数都可以用二进制表示。通过预处理2^k级祖先我们可以在O(logN)的时间内组合出任意步数的跳跃。这本质上是二进制拆分思想在树上的应用。选型考量优点在线算法无需预先知道所有查询思路清晰模板化程度高时间复杂度均衡预处理O(NlogN)查询O(logN)。缺点相比其他方法查询的logN因子在极端高频查询下可能成为瓶颈需要O(NlogN)的额外存储空间记录祖先信息。适用场景通用性强尤其适合查询并非一次性给出的动态场景如交互式问题或查询依赖前序结果的场景。2.2 Tarjan离线算法巧妙的“并查集与DFS”Tarjan算法展现了“离线处理”和“并查集”结合的魅力。它通过一次深度优先遍历就能回答所有预先知道的查询。核心思想算法在DFS遍历树的过程中将已访问完毕且回溯的子树“合并”到其当前父节点下使用并查集。当遍历到某个查询节点u时如果另一个节点v已经被访问过那么v所在集合的代表元并查集的根就是u和v的LCA。可以想象成在遍历过程中不断将已经摸清的“领地”合并并随时回答涉及已探索领地的询问。为什么用并查集并查集完美地维护了“已访问完毕的子树集合”并且可以快速找到这个集合的最高代表即当前子树的根也就是LCA候选。选型考量优点时间复杂度极优预处理O(NQα(N))近乎线性思想巧妙体现了离线处理的威力。缺点必须是离线算法需要提前知道所有查询递归DFS实现可能带来栈溢出风险对于深度很大的树需手动模拟栈理解和实现比倍增法稍复杂。适用场景所有查询一次性给出的静态场景且对效率要求极高。这是很多竞赛题的标准解法。2.3 树链剖分法重链上的“高速公路”树链剖分本身是一种将树“拍平”到线段树等数据结构上进行维护的强大技术。用它来求LCA可以看作是其一个“副产品”但效率非常高。核心思想通过两次DFS将树划分成若干条“重链”由重儿子连续连接形成的链。每个节点都记录所在重链的顶端节点。求LCA时比较两个节点所在重链的顶端将顶端深度较大的节点快速上提到其顶端节点的父节点处如此反复直到两个节点处于同一条重链上此时深度较小的节点就是LCA。为什么快重链剖分保证了从任意节点到根节点的路径上最多只会经过O(logN)条不同的重链。每次跳跃都是直接从当前节点跳到链顶跳过了链上所有节点从而将路径长度压缩到对数级别。选型考量优点查询复杂度也是O(logN)但常数通常比倍增法小树剖本身是非常有用的数据结构学会后可以解决一大类树上路径修改/查询问题。缺点预处理过程比倍增法复杂需要两次DFS代码量相对较大如果仅仅为了求LCA而学习树剖学习成本较高。适用场景当问题不仅仅是求LCA还涉及树上路径的权值修改、查询等操作时树链剖分是集成度更高的解决方案。2.4 RMQST表法转化为区间最值问题这种方法提供了一个全新的视角将LCA问题转化为序列上的RMQ区间最小值问题。核心思想对树进行欧拉序遍历DFS每次访问节点都记录得到一个长度为2N-1的序列。同时记录每个节点在欧拉序中第一次出现的位置。关键结论是两个节点的LCA等于它们第一次出现位置所构成的区间内深度最小的那个节点。这样我们只需要用一个支持O(1)查询的RMQ数据结构如ST表来维护欧拉序列中节点的深度即可实现O(1)的LCA查询。为什么是欧拉序欧拉序完整地记录了DFS的访问轨迹保证了任意两节点间的路径上的所有节点都会出现在它们第一次出现的位置之间的序列段中并且LCA恰好是其中深度最小的。选型考量优点查询速度最快达到O(1)适合海量查询ST表的构建思想也很经典。缺点预处理复杂度O(NlogN)且空间消耗较大存储欧拉序和ST表纯粹的查询算法不支持在线动态处理其他树上操作。适用场景适用于查询次数巨大Q远大于N且查询是离线的静态场景。在一些对查询时间极端苛刻的题目中会是首选。实操心得方法选择速查面对一道题如何快速选择查询是否离线是 - 优先考虑Tarjan理论最优或RMQ查询最多。查询是否在线或动态是 - 选择倍增或树链剖分。是否涉及路径上的其他操作如修改、求和是 -树链剖分是更全面的选择。是否只是单纯海量LCA查询是 -RMQST表可能最快。追求编码速度和稳妥-倍增法是万金油首选。3. 算法细节解析与模板实现理解了宏观思路我们来深入每种方法的实现细节并给出可直接使用的模板代码。我会用C作为示例语言并附上关键注释。3.1 倍增法模板详解倍增法的实现分为两大步预处理和查询。预处理阶段 目标是计算出fa[u][k]数组表示节点u向上跳2^k步后到达的祖先节点。通常设fa[u][0]为u的直接父节点。const int MAXN 100005; // 最大节点数 const int LOG 17; // 2^LOG MAXN 通常取17或20足够 vectorint tree[MAXN]; // 树的邻接表 int depth[MAXN]; // 节点深度 int fa[MAXN][LOG]; // 倍增祖先数组 // DFS预处理 depth 和 fa[u][0] void dfs(int u, int p) { // u当前节点 p父节点 fa[u][0] p; depth[u] depth[p] 1; for (int i 1; i LOG; i) { // 核心递推u的2^i祖先 (u的2^(i-1)祖先)的2^(i-1)祖先 fa[u][i] fa[fa[u][i-1]][i-1]; if (fa[u][i] 0) break; // 如果已经跳到根以上可以提前终止 } for (int v : tree[u]) { if (v p) continue; dfs(v, u); } }查询阶段 给定节点a和b求它们的LCA。对齐深度将深度较大的节点向上跳直到与另一个节点深度相同。跳跃时从大步长2^(LOG-1)开始尝试。同步上跳如果此时两个节点相同则它就是LCA一个节点是另一个的祖先。否则让它们一起向上跳从大步长开始尝试目标是跳到LCA的直接子节点。最后这两个节点的父节点就是LCA。int lca(int a, int b) { // 1. 确保a是深度较大的节点方便处理 if (depth[a] depth[b]) swap(a, b); // 2. 将a跳到与b同深度的位置 int diff depth[a] - depth[b]; for (int i 0; diff 0; i) { if (diff 1) { // 利用二进制位判断是否需要跳2^i步 a fa[a][i]; } diff 1; } // 更清晰的写法 // for (int i LOG-1; i 0; --i) { // if (depth[fa[a][i]] depth[b]) { // 如果跳了还在b下面或同层就跳 // a fa[a][i]; // } // } // if (a b) return a; // 处理b是a祖先的情况 // 3. 如果此时已经相同直接返回 if (a b) return a; // 4. a和b一起向上跳目标是LCA的直接子节点 for (int i LOG-1; i 0; --i) { // 如果跳了之后不相同说明还没到LCA可以跳 if (fa[a][i] ! fa[b][i]) { a fa[a][i]; b fa[b][i]; } } // 循环结束后a和b的父节点就是LCA return fa[a][0]; }注意事项LOG大小的选择LOG值应满足2^LOG N。通常N1e5时取17N1e6时取20即可。根节点的处理通常将根节点的父节点设为0depth[0] 0fa[root][0]0。这样在跳跃时跳到0节点是安全的表示跳出树了。递推顺序预处理DFS必须是先计算完当前节点的fa[u][i]再递归子节点确保子节点递推时父节点的信息已就绪。查询时的跳跃顺序务必从大到小尝试步长i从LOG-1递减到0这样才能像二进制拆分一样组合出任意步数。3.2 Tarjan离线算法模板详解Tarjan算法需要预先存储所有查询。我们使用并查集DSU来维护已访问节点的集合。const int MAXN 100005; const int MAXQ 100005; // 最大查询数 vectorint tree[MAXN]; vectorpairint, int queries[MAXN]; // queries[u] {v, query_id} int ans[MAXQ]; // 存储每个查询的答案 int parent[MAXN]; // 并查集父节点 int vis[MAXN]; // 标记节点状态0未访问1访问中2已访问并合并 // 简易并查集 int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int x, int y) { // 这里y是x的父节点简单合并即可 parent[find(x)] find(y); } void tarjan(int u) { vis[u] 1; // 标记为正在访问 for (int v : tree[u]) { if (vis[v]) continue; tarjan(v); unite(v, u); // 关键子节点v访问完毕将其集合合并到当前节点u // 此时以u为根的子树已全部访问并合并到u的集合下 } vis[u] 2; // 标记为已访问完毕 // 处理所有与u相关的查询 for (auto [v, id] : queries[u]) { if (vis[v] 2) { // 如果另一个节点v也已经访问完毕 ans[id] find(v); // 那么v所在集合的代表元就是LCA } } } // 主函数调用前准备 int main() { // ... 读入树 ... // ... 读入Q个查询 (a, b)并构建queries数组: queries[a].push_back({b, i}); queries[b].push_back({a, i}); for (int i 1; i N; i) parent[i] i; // 初始化并查集 tarjan(root); // 从根开始DFS // 输出 ans[0...Q-1] }注意事项查询的存储每个查询(a,b)需要双向存储到queries[a]和queries[b]中因为DFS过程中先访问到a或b是不确定的。合并时机一定要在递归子节点之后处理当前节点查询之前进行合并unite(v, u)。这保证了当处理u的查询时以u为根的子树已经合并到了u下但u本身还没有合并到它的父节点下因此find(v)返回的正好是u和v的LCA。状态标记vis[u]2表示u的所有子树都已处理完毕。只有另一个节点状态为2时才能确定其所在集合的代表元是LCA。栈溢出对于深度可能很大的树如链递归DFS可能导致栈溢出。可以使用显式栈进行迭代遍历但实现会复杂不少。3.3 树链剖分法模板详解树链剖分求LCA是其核心应用之一。我们需要预处理出以下信息son[u]: u的重儿子sz[u]: 以u为根的子树大小top[u]: u所在重链的顶端节点fa[u]: u的父节点dep[u]: u的深度const int MAXN 100005; vectorint tree[MAXN]; int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN]; int top[MAXN]; // 第一遍DFS求fa, dep, sz, son void dfs1(int u, int p) { fa[u] p; dep[u] dep[p] 1; sz[u] 1; son[u] -1; int maxSize 0; for (int v : tree[u]) { if (v p) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] maxSize) { maxSize sz[v]; son[u] v; } } } // 第二遍DFS求top连接重链 void dfs2(int u, int tp) { top[u] tp; if (son[u] ! -1) { dfs2(son[u], tp); // 重儿子继承当前链的顶端 } for (int v : tree[u]) { if (v fa[u] || v son[u]) continue; dfs2(v, v); // 轻儿子自己作为新链的顶端 } } // 树剖LCA查询 int lca(int a, int b) { while (top[a] ! top[b]) { // 当不在同一条重链上时 if (dep[top[a]] dep[top[b]]) swap(a, b); // 将深度较大的链顶节点向上跳 a fa[top[a]]; } // 此时a和b在同一条重链上深度较小的就是LCA return dep[a] dep[b] ? a : b; } // 初始化 void init(int root) { dfs1(root, 0); dfs2(root, root); }注意事项两遍DFSdfs1计算基本信息并确定重儿子dfs2进行重链剖分。顺序不能错。重儿子的定义子树大小最大的儿子。如果子树大小相同任选一个即可。top数组的赋值重儿子的top继承自父节点轻儿子的top是自己。这保证了重链的连续性。LCA查询逻辑核心是不断比较链顶深度将深度大的节点跳到其链顶的父节点。这个过程直到两者链顶相同。由于重链数量是O(logN)所以跳跃次数也是O(logN)。与倍增法对比树剖的logN常数通常更小因为它是基于树的重链性质而倍增是基于二进制。3.4 RMQST表法模板详解这种方法将树转化为欧拉序列并用ST表维护深度最小值。const int MAXN 100005; const int LOG 17; // 2^LOG 2*MAXN vectorint tree[MAXN]; int dep[MAXN]; int euler[2 * MAXN]; // 欧拉序列 int first[MAXN]; // 节点在欧拉序中首次出现的位置 int st[2 * MAXN][LOG]; // ST表存储欧拉序下标 int lg2[2 * MAXN]; // 预处理log2值 int idx 0; // 欧拉序索引 // DFS生成欧拉序和first数组 void dfs(int u, int p) { dep[u] dep[p] 1; first[u] idx; euler[idx] u; for (int v : tree[u]) { if (v p) continue; dfs(v, u); euler[idx] u; // 回溯时再次记录u } } // 预处理ST表维护的是深度最小的节点在欧拉序中的下标 void buildST() { int n idx; // 欧拉序列长度 // 预处理对数表 lg2[1] 0; for (int i 2; i n; i) lg2[i] lg2[i / 2] 1; // 初始化ST表st[i][0] i for (int i 0; i n; i) st[i][0] i; for (int j 1; (1 j) n; j) { for (int i 0; i (1 j) - 1 n; i) { int a st[i][j - 1]; int b st[i (1 (j - 1))][j - 1]; // 比较的是节点深度而非下标本身 st[i][j] (dep[euler[a]] dep[euler[b]]) ? a : b; } } } // RMQ查询返回欧拉序中[l, r]区间内深度最小节点的下标 int queryST(int l, int r) { int k lg2[r - l 1]; int a st[l][k]; int b st[r - (1 k) 1][k]; return (dep[euler[a]] dep[euler[b]]) ? a : b; } // LCA查询 int lca(int a, int b) { int l first[a], r first[b]; if (l r) swap(l, r); int pos queryST(l, r); // 得到深度最小节点的下标 return euler[pos]; // 返回该节点 } // 初始化 void init(int root) { dep[0] -1; // 方便根节点深度为0 dfs(root, 0); buildST(); }注意事项欧拉序列长度是2*N-1数组要开足够大。first数组记录每个节点第一次出现的位置这是查询区间的依据。ST表存储内容ST表st[i][j]存储的是区间[i, i2^j-1]内深度最小的节点在欧拉序euler中的下标而不是节点编号本身。比较时比较的是dep[euler[下标]]。查询区间LCA(a,b) 对应的RMQ区间是[first[a], first[b]]需保证左小右大。这个区间包含了从第一次访问a到第一次访问b之间DFS遍历的所有节点LCA的深度一定是其中最小的之一。空间与时间预处理O(NlogN)空间O(NlogN)查询O(1)。当N很大时logN倍的常数和空间消耗需要考虑。4. 实战对比与性能分析纸上得来终觉浅我们通过一个具体的例子来感受四种方法的差异。假设有一棵N10^5个节点的树Q10^6次查询。特性倍增法Tarjan离线法树链剖分法RMQST表法预处理时间O(N log N)O(N α(N))O(N)O(N log N)单次查询时间O(log N)O(α(N)) (近乎O(1))O(log N)O(1)总查询时间O(Q log N)O(NQ)O(Q log N)O(Q)空间复杂度O(N log N)O(NQ)O(N)O(N log N)算法类型在线离线在线离线编码复杂度简单中等中等偏难中等额外功能可求k级祖先仅LCA支持路径操作仅LCA适用场景通用动态查询静态大量查询需路径操作超大量静态查询分析Tarjan在静态查询下总时间最优但必须离线。RMQ查询最快但预处理和空间开销大也必须离线。倍增法是平衡的选择在线且编码简单是很多人的首选模板。树链剖分的查询常数小且功能强大是解决综合性问题的利器。实操心得性能测试中的坑常数问题时间复杂度的大O记号忽略了常数。例如树剖的logN常数通常小于倍增法。在N和Q都达到百万级别时这个差异会很明显。缓存友好性倍增法的fa[][]数组访问是跳跃的可能造成缓存命中率低。而树剖的top[],fa[]访问相对连续。在极端优化时需要考虑。递归开销Tarjan和DFS预处理如果递归太深需要改为迭代栈否则会Runtime Error栈溢出。内存限制RMQ法的ST表是O(N log N)的当N很大如1e6时st[2N][LOG]可能超过内存限制~2e6204B ≈ 160MB。需要权衡。5. 常见问题与调试技巧在实际编码和解题中会遇到一些典型问题。这里记录了我踩过的坑和解决方法。5.1 倍增法常见问题问题1查询结果错误经常返回0或错误节点。检查点1预处理DFS的递归基。确保根节点的fa[root][0] 0或-1等标识并且在递推fa[u][i] fa[fa[u][i-1]][i-1]时当fa[u][i-1]为0时fa[u][i]也应设为0避免访问非法内存。检查点2深度对齐的逻辑。确保在将深度大的节点a向上跳时判断条件是if (depth[fa[a][i]] depth[b])而不是if (fa[a][i] ! 0)。前者能正确处理b是a祖先的情况。检查点3同步上跳的循环。必须是for (int i LOG-1; i 0; --i)从大到小。并且判断条件是if (fa[a][i] ! fa[b][i])这保证了最后停在LCA的子节点。问题2程序在大型数据下超时。优化点1减少LOG大小。根据N精确计算所需的LOGLOG ceil(log2(N)) 1。优化点2使用链式前向星存图。如果树非常稠密边数多vectorint tree[MAXN]可能效率不如链式前向星。优化点3输入输出优化。使用scanf/printf或关闭同步的cin/cout。5.2 Tarjan算法常见问题问题答案部分正确部分错误。检查点1查询的存储。是否对每个查询(a,b)在queries[a]和queries[b]中都添加了ID是否对应正确检查点2并查集合并顺序。必须在tarjan(v)递归之后处理当前节点查询之前进行unite(v, u)。这个顺序是算法的核心。检查点3状态判断。只有当另一个节点vis[v] 2已访问完毕时find(v)的结果才是LCA。如果写成vis[v] 1得到的结果可能是错误的。检查点4并查集路径压缩。find函数中一定要有路径压缩parent[x] find(parent[x])否则复杂度会退化。5.3 树链剖分常见问题问题LCA查询陷入死循环或结果错误。检查点1dfs1中son[u]的初始化。如果没有重儿子应初始化为-1或0并在dfs2中做好判断。检查点2dfs2中重链的连接。重儿子调用dfs2(son[u], tp)继承链头轻儿子调用dfs2(v, v)自己作为新链头。检查点3LCA查询循环条件。while (top[a] ! top[b])内部比较的是dep[top[a]]和dep[top[b]]将深度大的链头节点a上提a fa[top[a]]。检查点4根的父节点设置。通常将根的父节点设为0且dep[0] 0。5.4 RMQ法常见问题问题查询返回的节点不是LCA。检查点1欧拉序生成。DFS回溯时是否再次记录了当前节点ueuler[idx] u;这句必须在递归子节点之后。检查点2first数组记录的是第一次出现的位置。在DFS第一次访问节点u时记录first[u] idx。检查点3ST表比较的是深度。st[i][j]存储的是最小深度节点的下标。在queryST和buildST中比较的是dep[euler[a]]和dep[euler[b]]而不是a和b。检查点4查询区间。l first[a],r first[b]务必保证l r。5.5 通用调试技巧小数据画图模拟用一棵5-6个节点的小树手工模拟算法的每一步尤其是数组值的变化与程序输出对比。这是最有效的定位逻辑错误的方法。打印关键数组在调试时打印出fa[][]倍增、parent[]Tarjan、top[]/son[]树剖、euler[]/first[]RMQ等数组检查是否符合预期。对拍写一个暴力求LCA的算法DFS向上爬用随机生成的大树和大量查询对比四种高效算法的结果是否与暴力结果一致。这是检验正确性的终极手段。边界测试测试LCA是根节点的情况、两个节点相同的情况、一个节点是另一个节点祖先的情况。6. 模板选择与扩展应用指南经过上面的详细拆解你应该对四种方法有了深入的理解。最后我分享一下在实际项目中如何选择和扩展这些模板。如何选择记住这个流程看查询是否离线离线 - Tarjan或RMQ在线 - 倍增或树剖。看功能需求只需LCA - 排除树剖除非学过了可能需要路径查询/修改 - 优先树剖。看数据规模N, Q 1e5四种方法均可选你最熟悉的。Q 极大 (1e6以上)离线RMQ法O(1)查询优势巨大。N 极大 (1e6以上)在线倍增法要小心LOG和空间树剖的常数可能更优。看个人熟练度比赛时优先使用你最熟悉、最不容易写错的方法。稳定输出比追求最优复杂度更重要。对于大多数人倍增法是这个角色。扩展应用倍增法很容易扩展来求树上两点的路径长度dist depth[a] depth[b] - 2*depth[lca]或者求一个节点的第k个祖先k级祖先问题。树链剖分其威力远不止LCA。结合线段树可以高效处理树上路径的权值修改、查询以及子树修改、查询。这是它最大的优势。Tarjan/RMQ它们是非常经典的离线算法和数据结构其思想可以迁移到其他问题上。例如Tarjan算法还可以用于求强连通分量、割点、桥等。我个人在竞赛和工程中的习惯是默认使用倍增法作为我的LCA模板因为它足够通用和可靠。只有当题目明确要求离线处理且查询量巨大时我会转向RMQ法。而如果题目涉及复杂的路径操作树链剖分则是必须祭出的武器。至于Tarjan它更像一个优美的理论解法在只需要LCA且离线的场景下它能提供最优雅的复杂度。理解这四种方法不仅仅是学会了四个模板更是掌握了四种重要的算法思想二进制倍增、离线处理与并查集结合、树链划分与路径压缩、以及将树问题转化为序列RMQ问题。这些思想会在你解决更多复杂问题时提供宝贵的思路。
