翻到之前的笔记，里面有一套“倍增法求解LCA”的模板，今天重新梳理了一遍，决定把整个过程写透。最近公共祖先（LCA，Lowest Common Ancestor）是树结构里最常碰到的操作之一，几乎只要涉及树的题目，迟早会遇到它。倍增法（Binary Lifting）的思路很简单：预处理每个节点向上走 2^k 步会到哪个节点，查询时用二进制拆分把一次 O(n) 的爬树过程变成 O(log n) 次跳步。这篇文章就从零开始，把定义、原理、代码、边界问题和实际应用一次讲完，适合刚接触树论、或者背过模板但没真正理解的人。

1. 先把LCA问题本身说清楚

1.1 什么叫祖先、什么又叫最近公共祖先

在讲算法之前，得先把概念抠准确。在一棵以 root 为根的有根树里，从某个节点出发，一直沿着父指针往上走，走到根节点，途中经过的所有节点都算这个节点的祖先。

有一个细节很多教程不提：节点本身算不算自己的祖先？不同资料定义不一样，但在倍增法的实现里，我们其实默认节点自己也能参与“祖先”的比较。正因为这样，当两个节点本身就存在祖先关系时，LCA 的结果才有可能是其中一个节点本身。

公共祖先的定义就顺理成章了：两个节点的祖先集合取交集，交集里的节点都是它们的公共祖先。因为根节点一定是所有节点的祖先，所以这个交集永远不为空。而“最近公共祖先”，就是交集中深度最大的那个节点，也就是离这两个节点最近的公共祖先。

举个例子。假设有一棵树，根是 1，1 的孩子是 2 和 3，2 的孩子是 4 和 5，3 的孩子是 6。那么 LCA(4,5)=2，LCA(4,6)=1，LCA(2,5)=2。最后一个例子值得多看一眼：因为 2 是 5 的祖先，所以 LCA 直接就是 2 本身，不需要继续往上找。

1.2 朴素做法为什么扛不住大数据

没有接触过倍增法的人，通常能想到两种暴力思路。

第一种是标记法。从 u 节点开始往上走，沿途经过的节点都打上标记；再从 v 节点往上走，遇到的第一个带标记的节点就是 LCA。思路非常直白，但每次查询都要重新标记和清空，单次查询最坏要走完一整条链，复杂度 O(n)，查询一多就彻底撑不住。

第二种是记录路径法。预处理时把每个节点到根的完整路径都存下来，查询时从根的方向往叶子方向比对，找到最后一个相同的节点。这个方法正确，但空间开销接近 O(n^2)，树稍微大一点就不可行。

最坏情况非常好构造：一棵退化成长的链，深度 n=100000，每次查询都查链两端的节点。暴力做法一次要爬 100000 步，再来 100000 次询问，总运算量就是 10^10 这个量级，任何评测系统都吃不消。所以问题的核心变成了：能不能预处理一些信息，让“向上走任意步”这件事变得很快？答案就是倍增法。

2. 倍增法的原理：两个关键视角

2.1 二进制拆分：把连续走步变成跳步

倍增法的巧妙之处，在于它预处理的不是“走一步到哪”，而是“走 2^k 步到哪”。

为什么够用？因为任意一个正整数都能拆成若干个 2 的幂之和，这就是二进制的性质。比如想从当前节点向上走 13 步，13 的二进制是 1101，等于 8+4+1，那只需要跳三下：先跳 8 步，再跳 4 步，再跳 1 步。也就是说，只要预处理出每个节点跳 1、2、4、8、16……步之后到达的位置，任意步数都能用最多 log2(n) 次跳跃组合出来。

这个思想和快速幂同源。快速幂把指数转成二进制来减少乘法次数，倍增法把“行走步数”转成二进制来减少跳步次数。

打个生活化的比方。一栋楼很高，电梯没有“直达任意楼层”的按钮，但给你几个快捷键：1层、2层、4层、8层、16层。你想去 13 层，按 8+4+1 三次就到；而普通电梯一层一层停，要走 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 就超了，最后会凑出 1+2+4+8=15，反而不对。这就是“大步优先、小步修正”的贪心策略，和位运算从高位往低位看是同一个逻辑。

3. 完整代码实现：从存图到AC

3.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，留足余量 vector<int> g[MAXN]; int depth[MAXN]; int up[MAXN][LOG]; void bfs(int root) { queue<int> 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 & (1<<j)，还可以写成下面的样子：

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)，常数非常小。实测 n=100000、q=100000 的随机数据，这份模板在普通机器上运行也就是几十毫秒，主要时间都花在读入和输出上。

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 >= n，j 至少是 ceil(log2(n))。对 n=100000 来说，2^17=131072，所以 LOG 取 18 其实已经够，下标是从 0 到 17。但为了省事，我通常直接写 20，多留两层余量，不管什么边界都不会越界。

如果 n 可能到 1000000，LOG 最好开到 21 以上。更稳妥的写法是动态计算：

int LOG = 1; while ((1 << LOG) <= n) ++LOG; vector<vector<int>> up(n + 1, vector<int>(LOG + 1));

动态开数组虽然比静态多写几行，但能彻底避免手算 LOG 出错，在比赛环境里更省心。

4.3 递归 DFS 到底能不能用

很多人习惯用递归 DFS 做预处理，代码确实更短，但有个隐患：如果树退化成一条长链，递归深度会达到节点数级别。n=100000 时，默认栈大小很容易爆掉。

现在的在线评测环境不一定给你开大栈，所以我的建议是：默认使用 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方法对比：

对绝大多数场景，我的选择是：学习阶段用倍增把原理吃透；比赛时不是特别卡常数，也用倍增；只有遇到离线题目、或者查询极其密集时才换 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 遇到链状树的滋味，真的不想再尝第二次。