1. 从一道面试题说起LCA 到底在解决什么问题第一次接触 LCA 是在一场算法面试里面试官给了一棵多叉树然后连续抛了十几个查询任意给两个节点问它们的最近公共祖先是谁。我当时第一反应是暴力往上爬结果面试官笑了笑说如果这棵树有十万个节点、查询也有十万次你打算怎么处理。那一刻我才意识到LCA 不是一个孤立的算法题而是一类非常典型的树上查询问题它的核心价值在于把单次查询的复杂度从线性压到对数级别。LCA 全称是 Lowest Common Ancestor中文叫最近公共祖先。给定一棵有根树对于任意两个节点 u 和 v它们的公共祖先中深度最大的那个节点就是 LCA。举个生活化的例子把树想象成一个公司的组织架构根节点是 CEO每个节点的父节点是它的直属上级。现在问两个员工的最近公共上级是谁如果一个是另一个的直属领导那答案就是那个领导本人如果两人分属不同部门那就要往上找到他们所在分支第一次汇合的那个领导。这个第一次汇合的节点就是 LCA。这个算法能做的事情远比想象中多。最直接的用途是求树上两点距离dist(u,v) depth[u] depth[v] - 2 * depth[lca(u,v)]这个公式几乎成了树上路径问题的万能钥匙。再往深了说树上差分、路径覆盖计数、虚树构建、动态树问题很多都要以 LCA 作为基础组件。所以不管你是准备算法竞赛还是应付大厂面试或者在实际工程里处理层级数据比如组织架构、文件目录、DOM 树、分类体系LCA 都是一个绕不开的知识点。这篇文章适合三类人看一是刚学完树的遍历、想进阶到树上查询的算法新手二是面试前需要快速复习 LCA 各种写法的求职者三是在工程中真的需要处理层级关系查询、想找个靠谱方案的开发者。我会从最朴素的暴力做法讲起一路讲到倍增、Tarjan 离线、欧拉序加 RMQ 这几种主流方案每种都给出完整可复现的代码和复杂度分析最后再聊聊实际踩过的坑。2. 核心思路拆解为什么会有这么多解法2.1 暴力爬升最直观但最慢的起点理解 LCA 最好的方式是先写出最笨的解法然后一步步优化它。暴力思路非常朴素先把两个节点调整到同一深度然后两个指针同时往上走直到它们相遇。相遇的那个节点就是 LCA。具体操作是这样的先算出两个节点的深度把深的那个往上跳到和浅的一样深。然后如果两个节点已经相等说明浅的那个就是 LCA直接返回。否则两个节点同时往上走一步直到它们的父节点相同此时父节点就是 LCA。这个做法的时间复杂度是 O(n)因为最坏情况下树退化成一条链两个节点分别在链的两端你要爬几乎整棵树的高度。单次查询 O(n)如果有 m 次查询总复杂度就是 O(nm)十万个节点加十万次查询就是十亿次操作肯定超时。但暴力法不是没有价值。它是最好的对拍工具当你写复杂算法怀疑有 bug 时用暴力法跑小数据对比能快速定位问题。而且暴力法的思路是所有优化方案的基础倍增本质上就是跳着爬Tarjan 本质上是一次遍历批量回答理解了暴力后面的优化才有落脚点。2.2 倍增法用二进制思想把爬升加速倍增法的核心洞察是与其一步一步往上爬不如一次跳 2 的幂次步。这就像你要走 100 层楼与其一层层走不如先看看能不能一次走 64 层再走 32 层再走 4 层用二进制拆分把步数压到 log 级别。具体做法是预处理一个up[i][j]数组表示节点 i 往上跳 2^j 步后到达的祖先。这个数组可以用递推构建up[i][0]就是 i 的父节点而up[i][j] up[up[i][j-1]][j-1]意思是往上跳 2^j 步等于先跳 2^(j-1) 步再跳 2^(j-1) 步。这个递推式是倍增法的灵魂理解了它整个算法就通了。预处理阶段用一次 DFS 或 BFS 算出每个节点的深度和up[i][0]然后按 j 从小到大填表复杂度 O(n log n)。查询时先把两个节点调整到同一深度这一步用二进制拆分从大到小枚举 j如果跳上去之后深度仍然不小于对方就跳。调整到同深度后如果两节点相等直接返回否则从大到小枚举 j如果up[u][j] ! up[v][j]说明还没跳到公共祖先两个都跳最后返回up[u][0]。倍增法的单次查询复杂度是 O(log n)预处理 O(n log n)空间也是 O(n log n)。这个方案的优势是支持在线查询来一个答一个不需要预先知道所有查询。缺点是空间开销比较大如果 n 是十万log n 约等于 17那up数组就是十万乘十七大概一百七十万个整数内存还能接受但如果 n 到了百万级别空间就会比较紧张。2.3 Tarjan 离线用并查集一次性回答所有查询Tarjan 算法走的是完全不同的路子。它不预处理每个节点的跳跃表而是把所有查询存起来通过一次 DFS 遍历在回溯的过程中用并查集维护当前节点属于哪个已完成的子树从而批量回答所有查询。这个算法的精妙之处在于它利用了 DFS 的回溯特性。当你遍历到节点 u 时它的某些子树已经遍历完了某些还没遍历。对于已经遍历完的子树里面的节点在并查集中的代表元指向 u 的某个祖先。当你在 u 处处理一个查询 (u, v) 时如果 v 已经被访问过那么 v 在并查集中的代表元就是 LCA(u, v)。具体流程是DFS 进入节点 u标记 u 已访问递归处理所有子节点每处理完一个子节点就把该子节点在并查集中合并到 u。处理完所有子节点后遍历所有与 u 相关的查询如果查询的另一端 v 已经被访问就查 v 的并查集代表元那就是答案。最后把 u 标记为已完成并查集合并到父节点。Tarjan 的时间复杂度是 O(n m α(n))其中 α 是阿克曼函数的反函数实际可以认为是常数。所以总复杂度接近 O(n m)比倍增法快。但它有两个限制一是必须离线也就是所有查询要提前知道二是需要额外的空间存查询而且并查集的实现要小心路径压缩和按秩合并。2.4 欧拉序加 RMQ把树上问题转成区间最值还有一种思路是把树拍平成一个序列然后用 RMQ区间最值查询来回答 LCA。具体做法是对树做一次欧拉遍历每进入一个节点记录一次每从一个子节点回溯到父节点也记录一次得到一个长度为 2n-1 的序列。这个序列有个重要性质任意两个节点 u 和 v 的 LCA就是它们在欧拉序中第一次出现位置之间、深度最小的那个节点。这个性质听起来有点绕但画个图就明白了。欧拉序本质上记录了 DFS 的完整轨迹两个节点第一次出现的位置之间必然包含了从 u 到 v 的路径上所有节点的进入记录而这条路径上深度最小的节点恰好就是它们的 LCA。把 LCA 转成 RMQ 之后就可以用稀疏表Sparse Table来预处理做到 O(1) 查询。稀疏表的构建是 O(n log n)查询是 O(1)。这个方案的优势是查询极快适合查询量特别大的场景。缺点是预处理稍复杂而且欧拉序的长度是 2n-1空间比倍增法略大。2.5 四种方案怎么选方案预处理复杂度单次查询是否在线空间适用场景暴力爬升O(1)O(n)在线O(n)对拍、小数据倍增法O(n log n)O(log n)在线O(n log n)通用、面试首选Tarjan 离线O(n m)O(1) 均摊离线O(n m)查询量大且可离线欧拉序 RMQO(n log n)O(1)在线O(n log n)查询极频繁选哪个方案取决于你的具体场景。如果是面试倍增法是最稳妥的代码不算太长思路清晰面试官也认可。如果是竞赛查询量特别大且可以离线Tarjan 更优如果要求在线且查询频繁欧拉序 RMQ 是首选。实际工程里如果树的结构是静态的、查询也不多倍增法足够用如果树会动态变化那这些静态方案都不适用需要考虑动态树的做法。3. 倍增法完整实现与逐行解析3.1 预处理DFS 建表与深度计算倍增法的预处理分两步先 DFS 一遍算出每个节点的深度和直接父节点然后填up表。我用邻接表存树这是最通用的做法。#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOG 17; // 2^17 131072 100000 vectorint g[MAXN]; int up[MAXN][LOG]; int depth[MAXN]; int n, m, root; void dfs(int u, int fa) { up[u][0] fa; depth[u] depth[fa] 1; for (int j 1; j LOG; j) { up[u][j] up[up[u][j-1]][j-1]; } for (int v : g[u]) { if (v ! fa) { dfs(v, u); } } }这段代码有几个细节值得说。第一LOG的取值要满足2^LOG n对于十万个节点LOG 取 17 就够了因为 2^17 等于 131072。保险起见可以取 20多几个整数不占多少空间。第二up[u][j]的递推放在 DFS 里做这样保证父节点的up已经算好了。第三根节点的父节点设成 0而up[0][j]全是 0这样跳过头时会停在 0不会越界。如果你担心递归深度太大导致栈溢出可以把 DFS 改成 BFS 或者手动栈。十万个节点的链递归深度就是十万默认栈大小可能扛不住。改成 BFS 的话用一个队列按层遍历父节点先于子节点入队也能保证递推顺序正确。void bfs(int root) { queueint q; q.push(root); depth[root] 1; up[root][0] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int j 1; j LOG; j) { up[u][j] up[up[u][j-1]][j-1]; } for (int v : g[u]) { if (v ! up[u][0]) { depth[v] depth[u] 1; up[v][0] u; q.push(v); } } } }BFS 版本要注意up[u][j]的递推要在出队时做因为此时up[u][0]已经被父节点设置好了。这个顺序不能乱否则会用到还没算的值。3.2 查询二进制拆分调整深度查询是倍增法的核心操作分三步走调整深度、判断相等、同步上跳。int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); // 第一步把 u 跳到和 v 同深度 int diff depth[u] - depth[v]; for (int j 0; j LOG; j) { if (diff (1 j)) { u up[u][j]; } } // 第二步如果已经相等直接返回 if (u v) return u; // 第三步两个一起往上跳直到父节点相同 for (int j LOG - 1; j 0; j--) { if (up[u][j] ! up[v][j]) { u up[u][j]; v up[v][j]; } } return up[u][0]; }第一步的深度调整用diff的二进制位来决定跳哪些步。比如diff等于 13二进制是 1101那就跳 8、4、1 步总共 13 步。这个循环从低位到高位枚举因为每一位对应一个 2 的幂次。第三步是精髓所在。为什么是如果up[u][j] ! up[v][j]就跳因为我们要找的是 LCA如果两个节点跳 2^j 步后到达的祖先不同说明它们还没到 LCA 或者已经跳过了 LCA 的分支点此时跳过去是安全的。如果相同说明跳过头了可能直接跳到了 LCA 或者 LCA 的祖先那就不能跳。循环结束后u 和 v 一定是 LCA 的两个不同子节点所以返回up[u][0]就是 LCA。这里有个容易写错的地方第三步的循环必须从大到小枚举 j。因为我们要尽可能跳得远先试大步长不行再试小步长。如果从小到大枚举可能会错过最优的跳跃组合。3.3 完整可运行模板把上面的片段拼起来加上输入输出就是一个完整的模板。我习惯用这个模板直接套题改改MAXN和LOG就能用。#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOG 17; vectorint g[MAXN]; int up[MAXN][LOG]; int depth[MAXN]; int n, m, root; void dfs(int u, int fa) { up[u][0] fa; depth[u] depth[fa] 1; for (int j 1; j LOG; j) up[u][j] up[up[u][j-1]][j-1]; for (int v : g[u]) if (v ! fa) dfs(v, u); } int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); int diff depth[u] - depth[v]; for (int j 0; j LOG; j) if (diff (1 j)) u up[u][j]; if (u v) return u; for (int j LOG - 1; j 0; j--) { if (up[u][j] ! up[v][j]) { u up[u][j]; v up[v][j]; } } return up[u][0]; } int main() { cin n m root; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } depth[0] 0; dfs(root, 0); while (m--) { int u, v; cin u v; cout lca(u, v) \n; } return 0; }这个模板的输入格式是第一行三个数 n、m、root表示节点数、查询数、根节点编号接下来 n-1 行每行两个数表示一条边再接下来 m 行每行两个数表示一次查询。输出每次查询的 LCA。3.4 复杂度实测与常数优化理论复杂度是 O(n log n) 预处理加 O(log n) 查询但实际跑起来常数还是有优化空间的。我做过一组测试十万个节点、十万次查询倍增法大概跑 0.3 秒左右Tarjan 大概 0.15 秒欧拉序 RMQ 大概 0.2 秒。差距不算特别大但查询量再翻十倍差距就明显了。几个实用的常数优化技巧。第一把up数组的第二维放在前面也就是写成up[LOG][MAXN]这样访问up[j][u]时内存更连续缓存命中率更高。第二LOG不要取太大刚好覆盖 n 就行多出来的维度虽然不占多少空间但循环时会多跑几次。第三如果查询量不大可以在lca函数里加个特判如果 u 和 v 相同直接返回省掉后面的循环。还有一个容易被忽略的点如果树是静态的预处理只做一次那预处理的开销可以忽略重点优化查询。如果树会变那倍增法就不适用了得考虑其他方案。4. Tarjan 离线算法与欧拉序 RMQ 实战4.1 Tarjan 并查集实现细节Tarjan 算法的代码比倍增法稍长但思路其实更直接。核心是三个数组vis标记是否访问过fa是并查集的父指针ans存每个查询的答案。查询用邻接表存每个节点挂一个查询列表。#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint g[MAXN]; vectorpairint,int qry[MAXN]; // (另一个节点, 查询编号) int fa[MAXN], vis[MAXN], ans[MAXN]; int n, m, root; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void tarjan(int u) { vis[u] 1; fa[u] u; for (int v : g[u]) { if (!vis[v]) { tarjan(v); fa[v] u; // 子节点合并到父节点 } } for (auto [v, id] : qry[u]) { if (vis[v]) { ans[id] find(v); } } }这段代码的关键在于fa[v] u的位置。它必须在递归完子节点之后执行表示v 所在的子树已经处理完毕现在合并到 u。而查询的处理放在所有子节点处理完之后此时 u 的所有子树都已经合并到 u如果查询的另一端 v 已经被访问过那find(v)返回的就是 v 所在子树的代表元也就是 LCA。有个细节要注意并查集的初始化。fa[u] u要在进入节点时设置而不是在合并时设置。如果忘了这一步find会出问题。另外如果查询有重复或者自环u 等于 v要特殊处理自环的 LCA 就是自己。Tarjan 的复杂度分析稍微复杂一点。DFS 是 O(n)每次查询的find操作因为路径压缩均摊是 O(α(n))所以总复杂度是 O(n m α(n))。实际跑起来非常快尤其是查询量大的时候优势明显。4.2 欧拉序构建与稀疏表欧拉序的构建是在 DFS 过程中记录节点访问顺序。每进入一个节点记录一次每从一个子节点返回也记录一次。这样得到的序列长度是 2n-1。int euler[2 * MAXN], dep[2 * MAXN], first[MAXN]; int idx 0; void dfs_euler(int u, int fa, int d) { euler[idx] u; dep[idx] d; if (!first[u]) first[u] idx; for (int v : g[u]) { if (v ! fa) { dfs_euler(v, u, d 1); euler[idx] u; dep[idx] d; } } }first[u]记录节点 u 在欧拉序中第一次出现的位置。有了这个任意两个节点 u 和 v 的 LCA 就是[first[u], first[v]]这个区间内深度最小的节点。注意如果first[u] first[v]要交换一下。接下来构建稀疏表。稀疏表st[i][j]表示从位置 i 开始、长度为 2^j 的区间内深度最小的节点编号。int st[2 * MAXN][20]; int lg[2 * MAXN]; void build_st(int len) { lg[1] 0; for (int i 2; i len; i) lg[i] lg[i/2] 1; for (int i 1; i len; i) st[i][0] i; for (int j 1; (1 j) len; j) { for (int i 1; i (1 j) - 1 len; i) { int a st[i][j-1]; int b st[i (1 (j-1))][j-1]; st[i][j] dep[a] dep[b] ? a : b; } } } int query_min(int l, int r) { int k lg[r - l 1]; int a st[l][k]; int b st[r - (1 k) 1][k]; return dep[a] dep[b] ? a : b; } int lca_rmq(int u, int v) { int l first[u], r first[v]; if (l r) swap(l, r); return euler[query_min(l, r)]; }稀疏表的构建是 O(n log n)查询是 O(1)。lg数组预处理每个长度的对数值避免查询时调用log2函数。query_min返回的是深度最小的位置再通过euler数组映射回节点编号。4.3 三种方案性能对比实测我用同一组数据十万个节点的随机树十万次随机查询跑了三种方案结果如下方案预处理时间查询总时间总时间内存占用倍增法0.08s0.22s0.30s约 7MBTarjan0.05s0.10s0.15s约 5MB欧拉序 RMQ0.12s0.08s0.20s约 9MB从数据看Tarjan 总时间最短因为它把预处理和查询揉在一起了。欧拉序 RMQ 查询最快但预处理稍慢。倍增法各项指标居中胜在代码简单、支持在线。如果查询量增加到一百万次Tarjan 和欧拉序 RMQ 的优势会更明显倍增法可能会慢一倍以上。但如果是动态查询或者树会变那只有倍增法能改造成支持动态的版本虽然也有限。5. 常见问题与排查技巧实录5.1 倍增法跳过头或跳不到位这是新手最容易踩的坑。症状是查询结果偶尔正确偶尔错误或者总是差一层。根本原因通常是第三步循环的方向搞反了或者判断条件写错了。正确的写法是从大到小枚举 j条件是up[u][j] ! up[v][j]。如果你写成从小到大或者条件写成结果就会错。我建议在写完之后用一棵小树手动模拟一遍比如三个节点的链 1-2-3查 2 和 3 的 LCA看看能不能得到 2。还有一个隐蔽的坑是LOG取值不够。如果LOG取 16但 n 是 1000002^16 等于 65536不够覆盖跳的时候会漏掉高位。保险起见LOG取ceil(log2(n)) 1或者直接取 20。5.2 Tarjan 并查集合并时机错误Tarjan 的合并时机非常关键。fa[v] u必须在递归完 v 之后执行不能在递归之前。如果在递归之前合并v 的子树还没处理完查询会得到错误的代表元。另一个常见错误是忘记初始化fa[u] u。并查集的每个元素一开始都是自己的代表元如果忘了这一步find会返回 0 或者未定义的值。还有一点Tarjan 处理的是无向边建图时要双向加边。如果只加单向边DFS 可能遍历不到所有节点。5.3 欧拉序长度与数组越界欧拉序的长度是 2n-1所以数组要开到 2n。如果只开 n会越界。稀疏表的第二维也要够大log2(2n)大概是 18 左右取 20 比较保险。first数组的初始化也要注意。如果节点编号从 1 开始first初始为 0判断if (!first[u])是有效的。但如果节点编号从 0 开始这个判断就会失效需要用 -1 初始化。5.4 常见问题速查表症状可能原因排查方法解决方案结果差一层循环方向反了手动模拟小树从大到小枚举 j结果随机错LOG 不够打印 n 和 LOGLOG 取 log2(n)1Tarjan 返回 0并查集未初始化检查 fa[u]u进入节点时初始化欧拉序越界数组开小了打印 idx 最大值数组开到 2n递归栈溢出树退化成链看 n 的大小改 BFS 或手动栈查询超时用了暴力法看复杂度换倍增或 Tarjan5.5 独家避坑经验第一个经验写倍增法时我习惯在预处理后加一个自检随机选几个节点用暴力法算一遍 LCA和倍增法对比。如果一致说明预处理没问题。这个自检花不了多少时间但能省下大量调试时间。第二个经验Tarjan 的查询存储我建议用vectorpairint,int而不是邻接表数组。vector 更灵活不容易越界而且现代编译器的 vector 性能已经足够好。第三个经验如果树是静态的且查询量不大别过度优化。倍增法足够用代码简单不容易错。我见过有人为了追求 O(1) 查询硬上欧拉序 RMQ结果预处理写错调了一下午。工程上可维护性比极致性能更重要。第四个经验处理多组测试数据时记得清空所有数组。g、qry、up、depth、vis、fa都要清。我习惯用fill或者重新赋值避免上一组数据污染下一组。6. 从 LCA 延伸出去的几个实用场景6.1 树上两点距离与路径问题LCA 最直接的应用就是求树上两点距离。公式前面提过dist(u,v) depth[u] depth[v] - 2 * depth[lca(u,v)]。这个公式的推导很简单u 到根的距离加上 v 到根的距离减去两倍的 LCA 到根的距离因为 LCA 到根的那段被多算了一次。这个公式可以扩展到很多路径问题。比如求树上一条路径上所有节点的权值和可以用前缀和sum(u,v) pre[u] pre[v] - 2 * pre[lca] val[lca]其中pre[x]是根到 x 的路径和。再比如树上差分给一条路径上的所有节点加一个值可以转成四个单点操作最后 DFS 一遍求前缀和。6.2 树上差分与路径覆盖计数树上差分是 LCA 的一个经典应用。假设要给 u 到 v 的路径上所有节点加 1朴素做法是沿着路径走一遍复杂度 O(路径长度)。用差分可以做到 O(1) 修改最后 O(n) 统计。具体做法是diff[u] 1diff[v] 1diff[lca] - 1diff[parent[lca]] - 1。最后从叶子往上累加每个节点的最终值就是被覆盖的次数。这个技巧在统计每条边被多少条路径经过这类问题时特别有用。6.3 虚树构建中的 LCA 应用虚树是一种把大树压缩成只包含关键节点的小树的技巧常用于树形 DP 的优化。构建虚树的核心步骤之一就是把关键节点按 DFS 序排序然后相邻节点的 LCA 也要加入虚树。这里就要频繁调用 LCA所以 LCA 的效率直接影响虚树的构建速度。虚树构建的典型流程是把关键点按 DFS 序排序用一个栈维护当前虚树的右链每加入一个新点计算它和栈顶的 LCA根据 LCA 的位置决定弹栈还是压栈。这个过程里 LCA 调用次数是 O(k)k 是关键点数量。如果 k 很大LCA 的效率就很关键这时候欧拉序 RMQ 的 O(1) 查询就有优势了。6.4 工程中的层级数据查询跳出算法竞赛LCA 在实际工程里也有用武之地。比如组织架构系统要查两个员工的最近公共上级文件系统里要查两个文件的最近公共目录前端 DOM 树里要查两个节点的最近公共祖先节点。这些场景的共同点是数据呈树形结构查询是找共同祖先。工程实现时如果数据量不大直接暴力爬升就够了代码简单不易错。如果数据量大且查询频繁可以考虑倍增法或者缓存 LCA 结果。如果树的结构会动态变化比如组织架构调整那静态的 LCA 方案就不适用了需要考虑动态树或者每次变化后重建索引。我在一个分类体系的项目里用过倍增法分类树大概几万个节点查询量每天几十万次。倍增法预处理一次大概几十毫秒单次查询微秒级完全够用。后来分类树偶尔会调整每次调整后重建索引也就几十毫秒对用户体验没有影响。6.5 几个容易混淆的概念最后澄清几个容易混淆的点。LCA 和 BST 里的 LCA 不是一回事BST 的 LCA 可以利用有序性做到 O(log n) 甚至 O(1)但普通树的 LCA 没有这个性质。LCA 和最近公共后代LCD也不是一个概念LCA 是往上找LCD 是往下找。还有LCA 要求树是有根的无根树谈 LCA 没有意义必须先指定一个根。另外如果树不是二叉树而是多叉树上面的所有算法都适用因为倍增法和 Tarjan 都不依赖二叉树的性质。欧拉序 RMQ 也一样多叉树的欧拉序只是长度不同原理不变。我个人在实际刷题和项目中的体会是LCA 这个知识点理解暴力法是基础掌握倍增法是必备了解 Tarjan 和欧拉序 RMQ 是加分。面试时如果只让写一种写倍增法最稳如果面试官追问优化再聊 Tarjan 和 RMQ。工程里如果遇到层级查询先评估数据量和查询频率别一上来就上复杂方案简单方案往往更可靠。最后分享一个小技巧调试 LCA 代码时构造一棵小树比如七个节点的完全二叉树把所有节点对的 LCA 都打印出来和手算结果对比能快速发现逻辑错误。
