我最早接触LCA最近公共祖先的时候第一反应是“这玩意儿能暴力做啊”直接从两个节点各自往上走到根把路径记下来找第一个重合点就行。思路没错但放到一棵十万个节点的树上单次查询最坏情况要遍历整棵树一组比赛数据跑下来TLE到怀疑人生。后来学了树上倍增才算真正把这个问题吃透——预处理O(nlogn)单次查询O(logn)这个复杂度在绝大多竞赛题和业务场景里都是够用的。这篇就写写C实现LCA树上倍增的那些事。适合刚接触树论算法的人也适合已经会写但想搞清楚“为什么这样跳”“边界怎么处理”的老手。我会把原理、代码、易错点、扩展应用全部拆开讲纯实战导向。1. 从暴力走到倍增一个必然的优化路径LCA的问题定义其实一句话就能说完在一棵有根树里两个节点的公共祖先中深度最深的那一个。但定义简单不代表好算关键在“怎么算得快”。1.1 暴力解法到底慢在哪很多初学者看到LCA的第一反应是“标记路径法”先从u节点往上走到根把沿途经过的节点全部打上标记然后从v节点往上走遇到的第一个带标记的节点就是LCA。这个做法在二叉树、链短的场景下没问题但它有两个致命缺陷。第一每次查询都要从查询节点走到根节点树的高度决定了单次查询的复杂度。遇到一条链状树每个节点只有一个子节点树高就是n单次查询最坏O(n)m次查询就是O(mn)数据规模一上来必挂。第二标记路径的做法需要额外的数据结构记录访问痕迹多次查询之间还要处理清空问题写起来也不干净。还有另一个暴力思路“从两个节点同时向上枚举深度”。也就是先把u和v调整到同一深度然后一层一层同时往上走直到找到第一个相等的节点。这种方法在随机数据下表现尚可但树形退化成链的时候依然是O(n)。暴力法的根本问题在于它把“向上走”看成了“一步一个节点”完全浪费了树的层次结构信息。1.2 倍增的思想用二进制换时间倍增优化的切入角度非常暴力——既然一步一个节点太慢那就“一步跳2的幂次个节点”。想象一下你从某个节点想要向上走13步暴力做法是一步一步数着走走13次。倍增的做法是把13拆成二进制13 8 4 1也就是说我分别跳8步、跳4步、跳1步三次操作就到位了。这就是倍增的核心预处理出每个节点向上跳2^0、2^1、2^2……2^k步分别能到哪个节点查询时把向上走的距离做二进制拆分把O(n)的纵向移动压缩到O(logn)次跳跃。这个思路之所以成立是因为向上跳这个动作满足“可合并性”从x向上跳2^{j-1}步到达y再从y向上跳2^{j-1}步得到的就是从x向上跳2^j步的位置。这不就是动态规划的状态转移吗预处理阶段就是做一个简单的DP。而查询阶段二进制拆分的逻辑本质上就是“从大到小尝试”我手里最多能跳2^k步我就先试着跳2^k步如果跳完还在目标深度之下就跳否则减小步长继续尝试。这个思路和二进制凑数的逻辑一模一样——你拿一张100元、一张50元、一张20元去凑130元肯定先用大面额去试试不动了换小面额。1.3 复杂度量化对比直接看数字感受一下差距。假设树上节点数n100000查询次数m100000树退化成链的最坏情况暴力标记路径法单次查询O(n)总耗时10^10次操作妥妥超时。倍增法预处理O(nlogn) ≈ 100000 × 17 ≈ 170万次操作单次查询O(logn) ≈ 17次跳跃m次查询约170万次操作。两者差了接近一万倍。这就是算法优化的魅力——没有改变问题的本质只是改变了你看待“向上走”这个动作的粒度。2. 预处理的核心环节DFS/ BFS建树与fa表、depth表的填充倍增算法落地第一步是准备工作建树、定根、算深度、填充倍增表。其中建图方式和遍历方式直接关系到代码的稳定性这里详细拆开说。2.1 图结构选型链式前向星还是vector邻接表树本质是无向图存图方式我见过两种主流写法和它们的拥趸。个人建议刷题阶段直接用vector邻接表代码短、好调试性能足够应对95%的场景。次优选择是链式前向星代码稍长但内存连续、常数更小适合大数据量和极端卡常的情况。// vector邻接表写法 #include vector vectorint G[MAXN]; void addEdge(int u, int v) { G[u].push_back(v); G[v].push_back(u); // 无向边 }// 链式前向星写法 struct Edge { int to, nxt; } edges[MAXN * 2]; int head[MAXN], ecnt 0; void addEdge(int u, int v) { edges[ecnt] {v, head[u]}; head[u] ecnt; }前向星用数组模拟链表遍历的时候通过nxt指针跳转优点是所有边存储在一块连续内存里cache友好空间开销也小。缺点是写起来繁琐容易在初始化head数组时漏掉memset。2.2 fa表的结构设计与状态转移方程这是整个算法最核心的预处理代码建议每一个变量都理解透彻再动手写。int LOG 20; // 根据n动态计算 int depth[MAXN]; int fa[MAXN][LOG]; // fa[u][j] 表示 u 节点向上跳 2^j 步到达的祖先节点 void dfs(int u, int parent) { depth[u] depth[parent] 1; fa[u][0] parent; for (int j 1; j LOG; j) { fa[u][j] fa[fa[u][j - 1]][j - 1]; } for (int v : G[u]) { if (v ! parent) { dfs(v, u); } } }重点拆解其中两个关键设计第一fa[u][0] parent处理的是“向上跳一步”的情况也就是2^01步父节点。这是整个倍增表的基础后续所有更高层都依赖这一层的正确性。第二状态转移方程fa[u][j] fa[fa[u][j - 1]][j - 1]的逻辑是先向上跳2^{j-1}步到达fa[u][j-1]再从这个中间节点向上跳2^{j-1}步总共就是2^j步。为什么能这么合并因为2^{j-1} 2^{j-1} 2^j指数加法的本质是幂次相乘。我在课堂上和学生讲过这件事的一个通俗比喻你想知道爷爷的爷爷是谁向上4步不用从自己开始一步步数先问你爸“你爷爷是谁”向上2步再问这个结果“他的爷爷是谁”再向上2步得到的答案就是从你向上4步的祖先。增量信息可以逐级复用这就是DP的使用场景。关于LOG取多大严谨的做法是LOG ceil(log2(n)) 1也就是树的最坏深度链状树时为n所需要的2的幂次加上一个保底。一般写比赛代码时我习惯直接定成LOG 20因为2^20 1048576覆盖100万量级的节点数没压力或者写成LOG 172^17 131072覆盖10万节点。懒的话就一次性开大一点LOG 25配2^25 ≈ 3300万别说竞赛题了工业场景都够。2.3 递归深度过大时的稳健替代方案用队列做BFSDFS实现简洁但有一个隐藏风险当树的形态是一条长链时递归深度就是n。以10万个节点为例DFS调用栈可能会因为递归深度过大而栈溢出取决于编译器和系统栈空间设置Linux默认栈通常8MB左右Windows下visual studio默认1MB很容易爆。如果n到了百万级别递归DFS基本就是“自杀”。这种情况下我推荐用BFS配合队列来做预处理逻辑完全一样只是遍历顺序从“递归深入”换成了“层序扩展”不存在栈溢出问题。void bfs(int root) { queueint q; q.push(root); depth[root] 1; fa[root][0] 0; // 根节点的父节点设置为00号节点不存在 while (!q.empty()) { int u q.front(); q.pop(); for (int j 1; j LOG; j) { fa[u][j] fa[fa[u][j - 1]][j - 1]; } for (int v : G[u]) { if (v ! fa[u][0]) { depth[v] depth[u] 1; fa[v][0] u; q.push(v); } } } }BFS写法的好处是不用关心系统栈的问题代价是队列操作比递归稍微多一点常数开销但可忽略不计。我自己写模板题时用递归遇到n超过50万或者题目明确说深度可能很大时就直接切BFS。另注有的题目是多组测试数据每组都要重新初始化depth数组和fa表。我见过不少人在这上面栽跟头——上一组的数据没清干净导致下一组查询时跳到了“野地址”。稳妥做法是在每组测试开始时memset掉head或vector清空并把depth整体置0。2.4 根节点的处理与fa数组的“哨兵”设计前面提到根节点的fa[root][0] 0这个0号节点是人为引入的“哨兵节点”它不代表树中真实存在的节点只是为了统一处理逻辑。这样做的意义在于如果root向上跳1步没有节点我们不特判而是指向0那么fa[0][j]递归往上跳也都是0所有越界跳跃自动收敛到0不需要额外的边界if。查询时判断“跳到0了吗”只需要最后统一检查。这种“人为引入无效节点统一处理边界”的手法遇到很多类似的树问题都非常实用。3. LCA查询的完整推导先对齐深度再同步上升预处理做完后树上任意两个节点的LCA查询逻辑已经定型了。核心思路分两步把深度大的节点拉到和小的一样然后两个一起往上跳到LCA的下一层。3.1 为什么必须先对齐深度假设两个节点一个深一个浅。如果不同步往上跳那么较高的那个节点往上跳之后可能直接越过LCA或者两个节点永远不在同一深度根本无法比较。所以第一步一定是“将u和v中深度较深的那个向上跳到与另一个相同深度”。这是整个查询算法的前置条件也是和“纯同步跳”思路之间最重要的区别。这里有一个容易产生疑问的点为什么对齐深度时是从大到小枚举二进制位因为我们要跳的距离可能是任意值二进制拆分里高位权重大低位权重小。我们要快速用尽可能少的跳数完成对齐从高位开始尝试如果跳完还没到目标深度就跳——这和用人民币凑金额时先试大面额是同一个道理。如果从低位开始凑可能跳了很多次还没到或者需要加上额外调整才能精准到达不优雅。3.2 标准查询函数的逐步解析int lca(int u, int v) { // 第一步让u成为更深的那个方便统一处理 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 fa[u][j]; } } // 此时u和v深度相等 if (u v) return u; // v本来就是u的祖先直接返回 // 第三步两个节点同时向上跳目标是跳到LCA的下一层 for (int j LOG - 1; j 0; j--) { if (fa[u][j] ! fa[v][j]) { u fa[u][j]; v fa[v][j]; } } // 此时u和v的父节点就是LCA return fa[u][0]; }逐行拆解一下第三步的逻辑——这是很多人最不理解的环节。为什么循环里判断的是fa[u][j] ! fa[v][j]而不是u ! v原因很简单如果我们直接判断u和v是否相等一旦u和v在上升途中相遇说明当前位置就是LCA直接返回即可。但大多数情况下u和v并不会恰好停在LCA上而是会越过它。越过的问题在于跳过头之后到达的节点就不再是公共祖先了你根本不知道自己“跳过头”了——算法无法区分“跳过头”和“还没到达LCA”因为你只比较了当前节点是否相等而越过之后两个节点的值依然不相等。正确做法是“每次判断两个节点的祖先是否相等”。如果fa[u][j] ! fa[v][j]说明它们跳2^j步后还没到达同一个节点即还没到LCA或超过LCA就大胆跳如果相等说明跳过头或者正好跳到LCA了就不能跳这一档而是缩小步长再试。循环结束后u和v位于LCA的“下一层”——也就是LCA的直接子节点——这时再往上一步就是LCA。有人可能要问为什么不直接跳到祖先相等的那个位置呢因为“祖先相等”可能有两种情况相等的位置恰好是LCA也可能是一个比LCA更高的祖先。我们最终要的是“最低”的公共祖先如果允许跳到LCA上方的公共祖先答案就是错的。只有让两个节点停在LCA的正下方才能保证再跳一步得到的正好是LCA——这是查询算法最终一步的精髓也是最容易让人卡壳的地方。3.3 查询时间复杂度为什么是O(logn)一次正确的查询第一步对齐深度枚举了LOG个二进制位最多走LOG次第三步从LOG-1遍历到0也是LOG次。所以查询复杂度O(LOG) O(logn)。预处理阶段DFS/BFS遍历每个节点时每个节点的fa表有LOG个元素要填所以总复杂度O(nlogn)。整体算法复杂度就是O(nlogn m·logn)n是节点数m是查询次数。在n≈10^5、m≈10^5的典型竞赛题里这个复杂度是标准答案水平。4. 模板完整落地方案与实测心得理解了原理之后关键就是把代码从头到尾拼完整并且能跑对。这里给一个可以直接使用的最小完整demo。4.1 可以直接抄的完整模板#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOG 20; vectorint G[MAXN]; int depth[MAXN]; int fa[MAXN][LOG]; void dfs(int u, int parent) { depth[u] depth[parent] 1; fa[u][0] parent; for (int j 1; j LOG; j) { fa[u][j] fa[fa[u][j - 1]][j - 1]; } for (int v : G[u]) { if (v ! parent) { 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 fa[u][j]; } if (u v) return u; for (int j LOG - 1; j 0; j--) { if (fa[u][j] ! fa[v][j]) { u fa[u][j]; v fa[v][j]; } } return fa[u][0]; } int main() { int n, m; cin n m; for (int i 1; i n; i) { int u, v; cin u v; G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); // 以1号节点为根 while (m--) { int u, v; cin u v; cout lca(u, v) \n; } return 0; }这份代码直接提交洛谷P3379模板题能过注意洛谷的根节点和节点编号没有特殊限制默认节点1为根即可如果题目指定根节点记得改dfs入口参数。4.2 踩过的坑汇总我前后教过不少学生写这个模板见过的bug主要集中在以下四个地方坑一LOGN开小了。如果树深度超过2^LOGfa数组查询时会越界产生随机值导致错误。建议LOG取20或直接算log2(n) 2多一位保底完全没副作用。坑二diff的二进制拆分方向写反。有些同学从LOG-1开始枚举diff这会导致当diff需要的高位二进制位时可能被跳过或重复跳。实际对齐深度时diff的二进制位到底哪些是1是不确定的所以只能从低到高枚举或者从高到低按位判断。标准写法是从低到高枚举j并判断diff的第j位也可以用for (int j 0; diff; j)写法边移位边判断。坑三第三步循环方向错。很多人把第三步写成从0到LOG-1递增枚举j这一下就崩了。必须从大到小枚举因为我们需要“优先尝试大步长跳不行再减小步长”这是贪心凑数思想的体现。如果从小到大会先把小的步长跳满剩下的距离可能无法用大幂次精确表示——其实也能算但逻辑会复杂很多而且很容易出错。一套标准的倍增模板这个循环方向必须是从大到小。坑四多组数据时fa表、depth表没有清零。有些题目是多组输入如果不清空fa和depth上一组数据的残留值会影响下一组查询。特别是fa[0][j]如果残留了非0值查询时会出现跳到一个幽灵节点的情况难排查。解法是在每组输入前对相关数组做memset或者重新初始化。4.3 实测场景选型建议结合我的实际做题经验把LCA的应用场景和选型建议整理成表供参考场景特征推荐方案原因静态树离线批量查询树上倍增或Tarjan离线倍增简单Tarjan复杂度O(n m)但需要离线处理树动态增删节点倍增配合动态加点每次更新fa表只影响新增节点及其祖先链查询量大且在线倍增表二分上升单次O(logn)在线也能扛住树深度极大十万级BFS预处理替代DFS避免递归栈溢出多次查询距离、路径倍增前缀和或差分基于LCA的路径拆解5. 扩展一击树上两点距离、路径最大值、树的直径学会LCA的模板之后千万别停在模板题。LCA的价值在于它作为“树上操作的基础设施”所有需要在树上做路径操作的题目都绕不开它。这里讲几个最常见的扩展。5.1 树上两点间距离这个几乎是LCA最直接的应用。两点的距离公式是dist(u, v) depth[u] depth[v] - 2 * depth[lca(u, v)]。为什么成立想象你把u到v的路径画出来它必然经过u往上一段、经过LCA、再往下一段到v。从根节点出发走到u一共depth[u]步走到v一共depth[v]步这两条路径在LCA处合拢。直接用depth[u] depth[v]会把LCA到根的那段重复计算两次减掉2倍即可。用途极广求两点之间走多少步、树的直径、连通性判断。举个例子题目要求查询树中两个节点之间的边权和或点权和只要在DFS时维护一个从根节点到当前节点的前缀和数组那么pathSum(u, v) prefix[u] prefix[v] - 2 * prefix[lca] value[lca]最后加回LCA本身的值因为减重复的时候把LCA也减掉了。5.2 需不需要支持“第k个祖先”这类查询倍增表天然支持“查询节点u向上跳k步到达的祖先”——把k拆成二进制按位跳。这个操作可以用来求解“从u到v路径上的第k个节点”等问题。做法是先判断k在u侧还是v侧如果在u侧直接从上往下跳k步如果在v侧先走到LCA再对称处理。这个扩展的核心还是二进制拆分和LCA查询时对齐深度的逻辑完全一致。用熟了之后你会觉得倍增这个思想像一个趁手的工具箱里面每一个工具都是同一套原理的变体。5.3 和Tarjan离线算法的选择前面一直说倍增其实LCA还有一个经典算法是Tarjan它用并查集DFS离线处理所有查询整体复杂度O(n m)。Tarjan在查询量巨大的时候优势明显因为它比倍增少一个log。但它有两个限制一是必须离线处理题目必须允许先把所有查询存下来再统一输出二是要写额外的并查集和回溯逻辑代码量比倍增多。我在实际比赛中更常用倍增主要是因为它写起来快、不容易错而且在线查询很灵活适用于交互式题目或者需要实时回答的场景。Tarjan我会留到查询量上百万且确定能离线的题目再考虑。5.4 树上路径最值/和值的一个小例子下面给一个小而美的示例查询一条路径上的点权和不考虑修改。思路就是维护一个从根到每个节点的点权前缀和数组。// 假设val[i]表示节点i的点权 // prefix[u]表示从根节点到u节点路径上的点权和不含根节点 long long prefix[MAXN]; void dfs(int u, int parent) { prefix[u] prefix[parent] val[u]; // 同步建fa和depth表的代码略 } long long querySum(int u, int v) { int l lca(u, v); return prefix[u] prefix[v] - 2 * prefix[l] val[l]; }注意最后要加回val[l]因为前缀和里LCA被减了两次但路径上是恰好应该算一次的。这个细节一开始很容易漏实际题目中LCA本身的贡献经常被丢掉导致答案差一个节点的值。6. 边界条件与性能细节那些隐藏的深坑写完LCA模板并通过样例之后真正的战斗才刚刚开始。边界、极端数据、性能常数这三个方向是决定代码成败的关键。6.1 根节点的深度和父节点初始化我习惯把根节点的depth设为1而不是0。原因在于距离公式depth[u] depth[v] - 2 * depth[lca]必须保证所有depth都是正数否则可能出现负数或零导致距离算错。根节点depth1时两个相同节点之间的距离是1 1 - 2*1 0正确。fa[root][0]设为0后要确保fa[0][j]也是0。做法是全局数组默认就是0但如果有多组测试数据需要显式将fa[0][j]置为0避免上一次数据写入了非0值。6.2 递归与栈溢出处理之前提过BFS替代DFS这里补充一个折中手段手工扩大递归栈。在Linux下可以用ulimit -s unlimited临时调大栈空间但比赛环境往往不允许Windows下visual studio可以调链接器栈大小但OJ上根本不生效。所以最稳妥的还是在写预处理时直接用BFS或者改用迭代栈模拟递归。我个人的习惯是只要节点数超过5万且不确定题目是否给足了栈空间就直接上BFS。6.3 使用快速IO优化当n和m都到10万级别标准cin/cout的同步流开销会让程序慢不少。模板题中我一般加这样两行ios::sync_with_stdio(false); cin.tie(nullptr);这两行可以显著提升cin/cout的速度。如果题目数据量到达百万级别或者卡IO常数建议直接上fread/fwrite自定义快读。实测下来快读能比cin快一个数量级。注意开了sync_with_stdio(false)后就不能混用scanf/printf了否则输入输出顺序会乱。6.4 邻接表内存的初始化与重用使用vector邻接表的时候如果多组测试数据记得对每组数据都执行for (int i 0; i n; i) G[i].clear();否则上一组的邻接关系会干扰当前组。这个坑我踩过不止一次——本地样例数据组数少看不出问题到了OJ上隐藏测试直接WA或RE排查半天最后发现是残留数据。如果使用链式前向星直接memset(head, -1, sizeof(head)); ecnt 0;即可。7. 从模板到实战典型题目拆解与对比理论讲完了用两道典型题目把LCA的实战流程走一遍顺便对比一下倍增方案在不同题目中的变化形态。7.1 题目类型一静态树上的基本LCA查询这类题目的典型代表是洛谷P3379输入给出一棵有根树和m组询问输出每组询问的LCA。直接套模板唯一要注意的是题目给的根节点可能不是1需要按照输入指定的根来做DFS。// 假设根为root dfs(root, 0);然后对每个查询lca(u, v)输出答案即可。这类题就是检验模板正确性的试金石。7.2 题目类型二树上两点距离 边权处理以P1967货车运输这类最大生成树LCA的综合题为例。这类题的思路是先跑最大生成树然后在这棵树上用LCA维护路径上的最小边权。做法是在预处理fa表的同时额外维护一个minEdge[u][j]数组表示节点u向上跳2^j步的路径中边权最小值是多少。int minEdge[MAXN][LOG]; // 初始化为INF dfs时 minEdge[u][0] weight(u, parent); // 到父节点的边权 minEdge[u][j] min(minEdge[u][j - 1], minEdge[fa[u][j - 1]][j - 1]);查询时在跳跃过程中同步更新答案的最小值即可。这种思路本质上是倍增表“缓存路径信息”的扩展应用——fa表缓存的是节点编号我们可以并行缓存路径上的最值、和值、异或和只要这个信息满足可合并性即可。7.3 倍增 vs 树链剖分什么时候必须换方案顺便提一句当题目需要“修改树上某条边的权值并查询路径信息”这种动态操作时倍增就撑不住了因为fa表中的缓存信息在修改后需要重新生成复杂度太高。这种场景应该上树链剖分线段树O(log^2 n)修改/查询。但纯粹的LCA查询倍增永远是最实用的首选。我在实际比赛中的经验法则是只要查询次数在10^5级别倍增完全够用。查询量达到10^6级别且是静态树可以直接上Tarjan离线。有修改操作的路径问题直接转向树链剖分别在倍增上加复杂操作硬扛。7.4 容错排查流程如果你写完LCA却怎么也过不了样例或者测试数据我建议按这个顺序排查问题先用小规模数据n≤10手算验证fa表是否正确特别是深度差和跳步方向。检查根节点选择的正确性题目有没有指定根。检查LOG是否足够大。检查第三层循环是不是从大到小遍历。检查是否存在多组数据而未清理干净的情况。如果是递归DFS爆栈换成BFS重写。反复犯的错永远是那几类——方向、范围、初始化。排查效率最高的方式就是对照这几个点逐项检查不要从头读代码碰运气。8. 写在用熟模板之后说实话LCA树上倍增是那种“一开始觉得难学会之后觉得也就那么回事”的算法。它真正的门槛不在于代码量而在于你是否完全理解“为什么最后一步只跳到LCA的下一层”“为什么第三步判断的是fa[u][j]和fa[v][j]而不是u和v”。只要把每一步背后的逻辑想通模板不需要背随时都能从原理推导出来。如果这篇文章能帮你把上面的几个“为什么”弄明白那它就完成了使命。剩下的就是多刷几道题把倍增从“会写”变成“写不错”。等你能在5分钟内无bug地敲完整个模板再回头看看最开始暴力标记路径的做法你会感觉到算法优化给人带来的那种畅快感——实实在在的一万倍的性能差距。