翻到之前的笔记里面有一套“倍增法求解LCA”的模板今天重新梳理了一遍决定把整个过程写透。最近公共祖先LCALowest Common Ancestor是树结构里最常碰到的操作之一几乎只要涉及树的题目迟早会遇到它。倍增法Binary Lifting的思路很简单预处理每个节点向上走 2^k 步会到哪个节点查询时用二进制拆分把一次 O(n) 的爬树过程变成 O(log n) 次跳步。这篇文章就从零开始把定义、原理、代码、边界问题和实际应用一次讲完适合刚接触树论、或者背过模板但没真正理解的人。1. 先把LCA问题本身说清楚1.1 什么叫祖先、什么又叫最近公共祖先在讲算法之前得先把概念抠准确。在一棵以 root 为根的有根树里从某个节点出发一直沿着父指针往上走走到根节点途中经过的所有节点都算这个节点的祖先。有一个细节很多教程不提节点本身算不算自己的祖先不同资料定义不一样但在倍增法的实现里我们其实默认节点自己也能参与“祖先”的比较。正因为这样当两个节点本身就存在祖先关系时LCA 的结果才有可能是其中一个节点本身。公共祖先的定义就顺理成章了两个节点的祖先集合取交集交集里的节点都是它们的公共祖先。因为根节点一定是所有节点的祖先所以这个交集永远不为空。而“最近公共祖先”就是交集中深度最大的那个节点也就是离这两个节点最近的公共祖先。举个例子。假设有一棵树根是 11 的孩子是 2 和 32 的孩子是 4 和 53 的孩子是 6。那么 LCA(4,5)2LCA(4,6)1LCA(2,5)2。最后一个例子值得多看一眼因为 2 是 5 的祖先所以 LCA 直接就是 2 本身不需要继续往上找。1.2 朴素做法为什么扛不住大数据没有接触过倍增法的人通常能想到两种暴力思路。第一种是标记法。从 u 节点开始往上走沿途经过的节点都打上标记再从 v 节点往上走遇到的第一个带标记的节点就是 LCA。思路非常直白但每次查询都要重新标记和清空单次查询最坏要走完一整条链复杂度 O(n)查询一多就彻底撑不住。第二种是记录路径法。预处理时把每个节点到根的完整路径都存下来查询时从根的方向往叶子方向比对找到最后一个相同的节点。这个方法正确但空间开销接近 O(n^2)树稍微大一点就不可行。最坏情况非常好构造一棵退化成长的链深度 n100000每次查询都查链两端的节点。暴力做法一次要爬 100000 步再来 100000 次询问总运算量就是 10^10 这个量级任何评测系统都吃不消。所以问题的核心变成了能不能预处理一些信息让“向上走任意步”这件事变得很快答案就是倍增法。2. 倍增法的原理两个关键视角2.1 二进制拆分把连续走步变成跳步倍增法的巧妙之处在于它预处理的不是“走一步到哪”而是“走 2^k 步到哪”。为什么够用因为任意一个正整数都能拆成若干个 2 的幂之和这就是二进制的性质。比如想从当前节点向上走 13 步13 的二进制是 1101等于 841那只需要跳三下先跳 8 步再跳 4 步再跳 1 步。也就是说只要预处理出每个节点跳 1、2、4、8、16……步之后到达的位置任意步数都能用最多 log2(n) 次跳跃组合出来。这个思想和快速幂同源。快速幂把指数转成二进制来减少乘法次数倍增法把“行走步数”转成二进制来减少跳步次数。打个生活化的比方。一栋楼很高电梯没有“直达任意楼层”的按钮但给你几个快捷键1层、2层、4层、8层、16层。你想去 13 层按 841 三次就到而普通电梯一层一层停要走 13 次。树上的爬升本质上也是这个道理。2.2 up数组的递推一次翻倍拼出大步预处理的核心是 up 数组定义如下up[u][j] 节点 u 向上跳 2^j 步后到达的节点如果跳出了根节点就记为 0代表一个不存在的哨兵节点。边界条件很简单up[u][0] father[u]也就是说向上跳 1 步就是父亲节点。关键的递推公式是up[u][j] up[up[u][j-1]][j-1]这句话要读出画面感从 u 向上跳 2^j 步等于先从 u 跳 2^(j-1) 步落到中间节点 x up[u][j-1]再从 x 继续跳 2^(j-1) 步。两次 2^(j-1) 拼接起来正好是 2^j。正是因为这个递推式预处理才不需要对每个节点都老老实实沿着链走而是自底向上、一层层翻倍整棵树的 up 值在 O(n log n) 时间内就能全部算完。2.3 查询的两个阶段先对齐再逼近拿到 up 数组后查询 LCA(u,v) 的过程分为两步。第一步是深度对齐。如果 depth[u] depth[v]就要把 u 向上跳 depth[u]-depth[v] 步。这个差值用二进制拆分成若干 2 的幂从大到小枚举 j能跳就跳。对齐之后两个节点站在同一高度后面的比较才有意义。对齐之后要做一次判断如果 u 和 v 已经相等了说明两个节点本来就有祖先关系较深的那个经过跳跃后正好追上了较浅的那个此时直接返回这个节点就是答案。第二步是一起向上跳。这里有一个容易误解的点我们不是直接跳到 LCA 上而是跳到 LCA 的下一层最后返回父节点。做法是从最大的 j 开始往下枚举如果 up[u][j] 和 up[v][j] 不相等就同时让 u 和 v 跳到 up[u][j] 和 up[v][j]。为什么这个条件成立当 up[u][j] ! up[v][j] 时说明跳完 2^j 步之后两个节点到达的位置不同也就是说这一跳没有跳到它们共同的祖先跳完之后两个节点仍然在 LCA 的下方可以放心跳。反过来如果 up[u][j] up[v][j]说明这一跳会落到某个公共祖先的位置可能正好是 LCA也可能直接越过 LCA 冲到根去了这种跳法是不允许的。循环结束后u 和 v 恰好停在 LCA 的两个直接子树里答案就是 up[u][0]也就是它们的父节点。为什么必须从大到小枚举 j还是回到二进制拆分的直觉。想凑出 13从大到小先取 8再取 4再取 1正好得到 13。如果从小到大先取 1、2、4凑到 7 之后再想取 8 就超了最后会凑出 124815反而不对。这就是“大步优先、小步修正”的贪心策略和位运算从高位往低位看是同一个逻辑。3. 完整代码实现从存图到AC3.1 树的存储方式树本质上是一个无环连通图我用邻接表存储每个节点一个 vector保存所有相邻节点。建图时因为是无向边所以要双向插入。3.2 预处理BFS写起来最稳预处理的核心任务是算出每个节点的 depth 和 up 数组。我推荐用 BFS 而不是递归 DFS原因后面会细说但先看代码。#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOG 20; // 2^17 131072 1e5留足余量 vectorint g[MAXN]; int depth[MAXN]; int up[MAXN][LOG]; void bfs(int root) { queueint q; q.push(root); depth[root] 0; for (int j 0; j LOG; j) up[root][j] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (v up[u][0]) continue; // 跳过父节点 depth[v] depth[u] 1; up[v][0] u; for (int j 1; j LOG; j) { up[v][j] up[up[v][j-1]][j-1]; } q.push(v); } } } int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); // 第一步深度对齐 int diff depth[u] - depth[v]; for (int j LOG - 1; j 0; --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() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; for (int i 0; i n - 1; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } bfs(1); while (q--) { int u, v; cin u v; cout lca(u, v) \n; } return 0; }这份模板可以直接拿去做裸 LCA 题。建图和查询都比较直观重点理解 bfs 里的 up 递推以及 lca 函数里两个循环的判断条件。3.3 深度对齐的两种写法深度对齐的循环除了用位运算 diff (1j)还可以写成下面的样子for (int j LOG - 1; j 0; --j) { if (depth[u] - (1 j) depth[v]) { u up[u][j]; } }两种写法本质是一样的都是保证 u 跳完不会比 v 更浅。第一种更接近二进制拆分的原始思路第二种可读性更好尤其适合 depth 从 1 开始计数的场景。我自己平时写第二种多一些因为判断条件看着更直观不容易让新手困惑。3.4 复杂度分析预处理阶段每个节点要填 LOG 个 up 值单次计算 O(1)所以预处理时间和空间都是 O(n log n)。单次查询只在两个循环里各枚举 LOG 次严格 O(log n)常数非常小。实测 n100000、q100000 的随机数据这份模板在普通机器上运行也就是几十毫秒主要时间都花在读入和输出上。4. 边界情况、踩坑与调优记录4.1 向上的跳步越界哨兵节点很重要树的高度是有限的向上跳 2^j 步很可能早就冲过根节点了。我的处理方式是统一把越界的祖先记为 0这样 up[u][j] 永远有值。但要注意up[0][j] 必须也是 0递推式 up[u][j] up[up[u][j-1]][j-1] 才能安全执行。全局变量默认是 0所以直接用全局数组没问题如果是局部数组一定要先 memset 或者显式初始化否则访问到随机地址出现什么结果都不奇怪。这个坑我一开始就踩过查了很久才意识到是初始化问题。4.2 LOG 到底取多少才安全LOG 的值不能拍脑袋定。树中任意节点向上跳的步数不会超过树的深度最大是 n-1。要表示 2^j nj 至少是 ceil(log2(n))。对 n100000 来说2^17131072所以 LOG 取 18 其实已经够下标是从 0 到 17。但为了省事我通常直接写 20多留两层余量不管什么边界都不会越界。如果 n 可能到 1000000LOG 最好开到 21 以上。更稳妥的写法是动态计算int LOG 1; while ((1 LOG) n) LOG; vectorvectorint up(n 1, vectorint(LOG 1));动态开数组虽然比静态多写几行但能彻底避免手算 LOG 出错在比赛环境里更省心。4.3 递归 DFS 到底能不能用很多人习惯用递归 DFS 做预处理代码确实更短但有个隐患如果树退化成一条长链递归深度会达到节点数级别。n100000 时默认栈大小很容易爆掉。现在的在线评测环境不一定给你开大栈所以我的建议是默认使用 BFS 版本纯迭代不会爆栈。如果非要用 DFS要么手动加栈要么确定题目数据保证树深很小否则遇到链状树就是一场灾难。4.4 森林和多连通块的处理有些题目给的并不是一棵树而是森林。处理办法也简单加一个虚拟根 0把所有连通块的实际根节点的父亲都指向 0然后从虚拟根开始做一次 BFS。这样整片森林在逻辑上变成一棵树。查询时如果两个节点最终不在同一个连通块里它们的 LCA 会算到虚拟根这时候需要自行判断是不是真正连通。4.5 输入输出优化1e5 级别的查询输入输出影响很大。cin 不关同步的话在某些评测机上可能比 scanf 慢很多。我通常这样优化ios::sync_with_stdio(false); cin.tie(nullptr);输出统一用 \n 而不是 endl因为 endl 会强制刷新缓冲区频繁刷新会拖慢速度。4.6 必测的边界用例每次写完模板我建议立刻手造几个边界用例跑一遍查询两个相同节点比如 lca(3,3)预期是 3。查询根和其他节点比如 lca(1,4)预期是 1。链状树1-2-3-4-5查询 lca(1,5)预期是 1这个用例能暴露递归爆栈和深度对齐问题。深度差正好是 2 的幂的两个节点用来检查对齐循环是否正确。这几个用例基本能覆盖 up 数组初始化、深度对齐、相等判断这三个最容易出错的位置。5. 倍增法和其他LCA算法的对比5.1 Tarjan离线算法Tarjan 算法利用 DFS 和并查集在遍历过程中回答所有询问。它把询问离线统一处理总复杂度 O(n q α(n))其中 α 是反阿克曼函数几乎可以看作线性。优点是快缺点是必须离线无法实现在线查询而且在算法竞赛中需要把所有询问先存下来。5.2 树链剖分树链剖分通过轻重链划分配合 top 数组和 fa 数组向上跳链。单次查询 O(log n)空间 O(n)在线比倍增省空间。但代码明显更长新手很容易在链跳跃的逻辑里绕晕。如果题目本身就需要树链剖分处理路径修改顺手用它求 LCA 是顺带的只是为了 LCA倍增更轻量。5.3 RMQ加欧拉序把树转成欧拉序后LCA 问题变成区间最小值查询可以用 ST 表做到预处理 O(n log n)、查询 O(1)。查询常数确实比倍增小但欧拉序长度是 2n-1细节多编码量也不小。只有查询次数极大、对查询效率极度敏感的时候我才考虑这种写法。常用LCA方法对比方法预处理复杂度单次查询复杂度在线/离线空间代码量倍增法O(n log n)O(log n)在线O(n log n)中朴素暴力O(1)O(n)在线O(n)少TarjanO(n)O(1) 摊还离线O(n)中树链剖分O(n)O(log n)在线O(n)较长RMQ欧拉序O(n log n)O(1)在线O(n log n)较长对绝大多数场景我的选择是学习阶段用倍增把原理吃透比赛时不是特别卡常数也用倍增只有遇到离线题目、或者查询极其密集时才换 Tarjan。6. LCA的实际应用场景6.1 两点之间的最短路径长度树上两点间唯一路径的长度是 LCA 最经典的应用dist(u, v) depth[u] depth[v] - 2 * depth[lca(u,v)]这个公式理解起来很直观从 u 到 v 的路径可以看成 u 向上走到 LCA再从 LCA 向下走到 v。两段深度差相加正好就是完整路径长度。6.2 树上差分处理“把路径 u-v 上所有节点或边的权值加 x”这类问题时通常使用差分数组。点权差分的写法是diff[u]diff[v]diff[lca]--diff[father(lca)]--如果是边权差分通常把边权下放到子节点写成diff[u]diff[v]diff[lca] - 2最后从底向上做一次累加就可以得到每个点被覆盖的次数。这一步里 LCA 算得准不准直接决定整个差分的结果所以模板必须稳。6.3 判断祖先关系和连通块归属判断 u 是否是 v 的祖先可以用深度加 LCA如果 lca(u,v) u 且 depth[u] depth[v]那么 u 就是 v 的祖先。这个技巧在很多树上数据结构题里都会出现。如果在森林中判断两个节点是否在同一棵树里先找到各自的根节点再比较即可。结合前面说的虚拟根处理这部分逻辑可以统一封装在 LCA 函数内部。6.4 倍增思想的扩展学会了倍增法求 LCA其实等于掌握了一套通用的跳表框架。往深处扩展还能做求路径上第 k 个节点先往上跳到 LCA再分两段向下数。维护路径最大值、最小值、异或值在 up 数组里额外存一份信息查询时同步合并。树上可持久化操作倍增表本身就是一种层次化预处理很多问题都能复用这份结构。所以说学透倍增法不只是为了一道 LCA 模板题后面很多树上倍增题都是同一套思想的变体。最后聊一点个人经验。倍增法 LCA 代码不算长但第一次写的人几乎都会在 up 数组初始化、深度对齐和第二段循环条件这三处犯至少一个错误。我的建议是别硬背模板先亲手把“跳 2^k 步”的递推公式推导一遍把二进制拆分的直觉建立起来再动手写代码。还有一个调试技巧很实用写一个小脚本随机生成树和询问再用暴力爬升法跑一遍结果和倍增法结果对拍。这种方法能在一分钟内暴露模板里的边界问题比自己一行行盯代码高效得多。另外比赛时记得默认使用 BFS 预处理的版本递归 DFS 遇到链状树的滋味真的不想再尝第二次。