1. 从一道面试题说起为什么LCA值得花时间搞透第一次接触LCA是在刷题的时候题目很直白给一棵树多次询问两个节点的最近公共祖先。当时我的第一反应是暴力——两个节点分别往上走标记走过的路径第一个相遇的节点就是答案。这个思路没错但复杂度是O(N)每次查询遇到N和Q都到1e5的数据规模直接超时。后来才知道LCALowest Common Ancestor最近公共祖先是树结构上最基础也最高频的查询操作之一。它的应用远不止刷题文件系统的路径查找、Git分支的合并基点计算、生物信息学里的进化树分析、网络路由中的拓扑关系判断底层都会用到LCA或者它的变体。可以说只要你的数据组织成了树形结构LCA就是绕不开的基本功。这篇文章我打算把LCA的几种主流解法从头到尾捋一遍包括暴力法、倍增法、Tarjan离线算法、欧拉序RMQ以及树链剖分求LCA。每种方法我都会说清楚它的核心思想、适用场景、复杂度分析以及我在实际写代码时踩过的坑。不管你是刚学完DFS想找个练手项目还是已经刷了几百题想系统整理模板这篇应该都能帮到你。2. LCA到底在解决什么问题2.1 用生活场景理解最近公共祖先先把这个概念说清楚。想象一个公司的组织架构图CEO在顶端下面是各级管理者最底层是普通员工。这个结构天然就是一棵树。现在有两个员工比如市场部的小A和技术部的小B我想知道他们俩在组织架构里“最近的共同上级”是谁。这个共同上级就是LCA。注意“最近”两个字很关键。CEO是所有员工的公共祖先但不是最近的。我们要找的是深度最大的那个公共祖先也就是离两个节点最近的那个。形式化地说给定一棵有根树对于任意两个节点u和vLCA(u,v)是同时满足以下两个条件的节点ww是u的祖先或u本身w是v的祖先或v本身且w的深度尽可能大。这里“祖先”包括节点自身这个约定很重要后面写代码时边界处理全靠它。2.2 为什么暴力法不够用最朴素的思路是这样的先把u到根节点的路径全部标记出来然后让v从自身开始往上走遇到的第一个被标记的节点就是LCA。这个做法单次查询最坏是O(N)如果树退化成一条链每次查询都要走完整条链。另一种暴力是先把两个节点调整到同一深度然后一起往上走直到相遇。这个做法在树比较平衡的时候表现还行但同样最坏O(N)。问题在于实际场景中查询次数Q往往很大。如果N1e5Q1e5暴力法就是1e10次操作完全不可接受。所以我们需要预处理把单次查询的复杂度降下来。这就是各种LCA算法的核心目标用预处理时间换查询时间。2.3 几种解法的复杂度对比在深入细节之前先给一个全局的复杂度对照表方便你根据题目数据范围快速选型。算法预处理时间单次查询时间空间复杂度适用场景暴力法O(N)O(N)O(N)数据量极小或只查询一两次倍增法O(N log N)O(log N)O(N log N)在线查询通用性最强Tarjan离线O(N α(N))O(1)O(N)查询全部已知可离线欧拉序RMQO(N log N)O(1)O(N log N)在线查询追求极致查询速度树链剖分O(N)O(log N)O(N)需要同时支持路径修改等操作这张表建议存下来。实际做题时先看Q和N的量级再看是否强制在线基本就能锁定用哪种方法。下面逐个展开。3. 倍增法最通用的在线LCA解法3.1 倍增的核心思想倍增法的本质是“二进制拆分”。任何一个正整数都可以拆成若干个2的幂之和比如13 8 4 1。倍增法利用这个性质让节点每次可以往上跳2的幂次步而不是一步一步走。具体来说我们预处理一个二维数组up[i][j]表示节点i往上跳2^j步后到达的节点。这个数组的递推关系非常优雅up[i][j] up[ up[i][j-1] ][j-1]翻译成人话就是从i往上跳2^j步等于先从i跳2^(j-1)步到达某个中间节点再从这个中间节点跳2^(j-1)步。这个递推是倍增法的灵魂理解了它整个算法就通了一半。预处理的时候用DFS或BFS遍历树同时记录每个节点的深度depth[i]和直接父节点up[i][0]。然后按j从小到大填表。由于up[i][j]依赖up[i][j-1]所以j必须在外层循环。3.2 查询过程的分步拆解查询LCA(u, v)分两个阶段。第一阶段是“对齐深度”。如果u和v深度不同先把深的那个往上跳到和浅的同一深度。这里用二进制拆分假设深度差是d我们从高位到低位枚举j如果d的第j位是1就把深节点往上跳2^j步。由于d的二进制表示唯一这个跳跃过程是精确的。第二阶段是“同步上跳”。此时u和v在同一深度。如果它们已经相等那LCA就是它们自己这就是为什么祖先要包括自身。否则从高位到低位枚举j如果up[u][j] ! up[v][j]说明跳2^j步后两者还没相遇那就同时跳。循环结束后u和v一定停在LCA的正下方所以答案是up[u][0]。这里有个容易写错的地方判断条件是up[u][j] ! up[v][j]而不是。很多人第一次写会搞反。想清楚逻辑我们要找的是最深的那个“两者还没相遇”的位置然后答案就是再往上一步。3.3 代码模板与关键细节#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOG 17; // 2^17 1e5 vectorint g[MAXN]; int up[MAXN][LOG]; int depth[MAXN]; int n, q; 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]; }这段代码有几个细节值得说。第一LOG的取值要满足2^LOG N对于1e5的数据LOG17就够了但保险起见可以开到20。第二dfs里先设置up[u][0]再递推其他j顺序不能乱。第三根节点的父节点设成0或自己up[0][j]全部为0这样跳过头也不会越界。注意如果树不是以1为根需要先找到根节点再dfs。另外多组测试数据时记得清空邻接表和up数组否则会WA得很惨。3.4 倍增法的实操心得我在实际写倍增法时踩过几个坑分享出来帮你省时间。第一个坑是数组开小。up数组是MAXN × LOG如果LOG开成20MAXN是1e5那就是2e6个int大约8MB一般不会超。但如果题目N到5e5LOG就要开到20以上内存要算清楚。第二个坑是递归爆栈。树退化成链时dfs递归深度到NC默认栈可能撑不住。解决办法是改用BFS预处理或者手动开大栈空间。BFS的写法也不复杂用队列按层遍历父节点先于子节点入队处理顺序天然满足递推要求。第三个坑是深度数组的初始化。如果根节点深度设为0那depth[fa]在fa0时是0depth[u]1没问题。但如果根节点深度设为1就要保证depth[0]0否则根节点的深度会算错。4. Tarjan离线算法查询多且可离线的利器4.1 离线思维与并查集配合Tarjan算法是离线算法意思是它需要一次性读入所有查询统一处理后输出答案。如果你的题目允许离线即不需要边读边答并且查询次数很多Tarjan是很优雅的选择。它的核心是DFS遍历加并查集。DFS过程中每个节点有三种状态未访问、正在访问在递归栈中、已访问完成。当DFS到某个节点u时遍历所有与u相关的查询(u, v)如果v的状态是“已访问完成”那么LCA(u,v)就是v在当前并查集中的祖先。这个结论的直觉理解是v已经完成了DFS说明v所在的子树已经处理完毕而u正在访问说明u在v的某个祖先的子树里。并查集把已完成子树的节点都指向了它们当前能追溯到的最高祖先这个祖先恰好就是LCA。4.2 算法流程与伪代码// 伪代码展示核心逻辑 void tarjan(int u) { fa[u] u; // 并查集初始化 vis[u] 1; // 标记正在访问 for (int v : g[u]) { if (!vis[v]) { tarjan(v); fa[v] u; // 子树处理完合并到u } } // 处理与u相关的查询 for (auto [v, id] : queries[u]) { if (vis[v] 2) { // v已完成访问 ans[id] find(v); } } vis[u] 2; // 标记完成 }这里vis数组用1表示正在访问2表示已完成。查询用邻接表存每个查询存两份u存vv存u方便双向处理。ans数组按查询编号存答案。4.3 Tarjan的适用边界与注意事项Tarjan的时间复杂度是O(N Q α(N))其中α是阿克曼函数的反函数实际可以认为是常数。所以它几乎是线性的非常快。但它有几个限制。第一必须离线所有查询要预先知道。第二并查集的路径压缩要写对find函数用递归或迭代都行但要注意压缩后父指针的变化。第三vis数组的状态判断不能搞混只有vis[v]2时才能用find(v)作为答案vis[v]1说明v还在栈中此时v是u的祖先但LCA还没确定。实操提示如果查询里出现uv的情况Tarjan也能正确处理因为此时v的状态是1正在访问不会被误判。但倍增法里uv会在对齐深度后直接返回也没问题。两种方法对自查询都安全。5. 欧拉序加RMQ把LCA变成区间最值5.1 欧拉序的构造与性质欧拉序是DFS遍历树时每次进入节点或回溯到节点都记录一次得到的序列。比如一棵树1-2, 1-3欧拉序是1 2 1 3 1。这个序列有个重要性质任意两个节点u和v的LCA就是欧拉序中u第一次出现位置和v第一次出现位置之间深度最小的那个节点。这个性质把LCA问题转化成了RMQ区间最小值查询问题。RMQ有成熟的解法比如ST表稀疏表预处理O(N log N)查询O(1)。5.2 ST表的构建与查询ST表的核心是st[i][j]表示从位置i开始长度为2^j的区间的最小值。递推关系是st[i][j] min(st[i][j-1], st[i 2^(j-1)][j-1])查询区间[l, r]时令k log2(r - l 1)答案是min(st[l][k], st[r - 2^k 1][k])。两个区间可能有重叠但min操作满足幂等性重叠不影响结果。在LCA场景中st表存的是深度最小的节点编号。构建时先求欧拉序和每个节点的首次出现位置first[u]然后对欧拉序的深度数组建ST表。5.3 欧拉序方法的优劣分析欧拉序RMQ的查询是严格O(1)比倍增法的O(log N)更快。如果查询量极大比如1e6次这个方法有优势。但它的预处理常数比倍增法大。欧拉序长度是2N-1ST表要开(2N) × log(2N)空间比倍增法大。而且代码量更多需要维护欧拉序、深度数组、首次出现位置、ST表四个结构写起来容易出错。我的建议是如果题目没有卡常到极致倍增法足够用。欧拉序方法更适合作为知识储备理解它有助于你建立“不同问题之间可以相互转化”的思维。6. 树链剖分求LCA顺带解决路径问题6.1 重链剖分的基本概念树链剖分HLD本来是用来解决树上路径修改和查询的但它顺带也能求LCA。剖分的做法是每个节点选一个“重儿子”子树最大的儿子从节点到重儿子的边叫重边连续的重边构成重链。每个节点记录它所在重链的顶端top[u]。求LCA时不断把top深度较大的那个节点跳到top的父节点直到两个节点在同一条重链上。此时深度较小的那个就是LCA。6.2 剖分求LCA的代码实现int lca_hld(int u, int v) { while (top[u] ! top[v]) { if (depth[top[u]] depth[top[v]]) swap(u, v); u fa[top[u]]; } return depth[u] depth[v] ? u : v; }这段代码短得惊人但前提是你要先做两遍DFS第一遍求子树大小、重儿子、深度、父节点第二遍求top。预处理O(N)单次查询O(log N)。6.3 什么时候选树链剖分如果你只需要求LCA倍增法更简单。但如果题目还要求路径上的权值修改、路径求和、路径最值等操作树链剖分就是首选因为LCA只是它的副产品。这种情况下用剖分可以一套代码解决多个问题不用写两套逻辑。7. 常见问题与排查技巧实录7.1 倍增法WA的几种典型原因症状可能原因排查方法答案偏深同步上跳时判断条件写反检查是!还是答案偏浅对齐深度时漏跳或多跳打印diff的二进制逐位验证部分查询错LOG开太小确保2^LOG N全部错根节点父指针未初始化up[root][0]设为0或root多组数据错数组未清空每组数据前memset7.2 深度对齐的二进制验证技巧对齐深度那段代码如果结果不对最直接的调试方法是在循环里打印每次跳跃前后的节点和深度。另外可以手算一个例子假设diff5二进制101应该跳2^0和2^2即跳1步和4步总共5步。如果代码跳了别的组合说明位运算写错了。7.3 递归改迭代的实操方案递归DFS在链状树上会爆栈。改成BFS的写法如下void bfs(int root) { queueint q; q.push(root); depth[root] 0; 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]的递推放在出队时做因为此时u的up[u][0]已经确定。入队时只设置up[v][0]和depth[v]其他j等v出队时再算。8. 选型建议与实战体会8.1 根据题目特征快速选型拿到题目先看三个信息N的范围、Q的范围、是否强制在线。N和Q都小比如1000以内暴力法最省事。N大Q大且在线倍增法。N大Q大且可离线Tarjan。Q极大1e6以上且在线欧拉序RMQ。需要路径操作树链剖分。8.2 我个人的模板管理习惯我习惯把倍增法的模板单独存一个文件变量名固定MAXN、LOG、g、up、depth。每次新题直接复制改MAXN和LOG加读入和输出。这样不容易在细节上翻车。Tarjan和欧拉序的模板也各存一份但用得少每次用之前会重新过一遍逻辑。8.3 一个容易被忽略的边界情况如果查询的两个节点中有一个是另一个的祖先倍增法在对齐深度后会发现uv直接返回。Tarjan在vis[v]1时不会处理等u完成后再处理时v已经完成find(v)会返回正确的祖先。欧拉序方法中两个位置的区间最小值就是那个祖先节点。三种方法都能正确处理但前提是代码逻辑没写错。建议专门测一组“祖孙查询”的数据。最后分享一个我常用的调试技巧写一个暴力LCA函数对拍。随机生成一棵树和若干查询比较倍增法和暴力法的输出。如果全部一致基本可以确定倍增法写对了。这个方法帮我省了无数次提交WA的时间。