倍增求 LCA
通过倍增预处理祖先表，在 O(log n) 时间内查询两个节点的最近公共祖先。
一句话算法
倍增 LCA 先让深的点向上跳到同一层，再让两个点一起从大步到小步向上跳。
问题模型
给定一棵有根树，需要多次查询两个点 u 和 v 的最近公共祖先。
“最近公共祖先”
在一棵有根树中，u 和 v 的公共祖先里，深度最大的那个节点叫做它们的最近公共祖先，记作 lca(u, v)。
常见扩展查询：
- 两点距离：
depth[u] + depth[v] - 2 * depth[lca(u, v)]。 - 判断祖先关系。
- 树上路径拆分。
- 树上差分。
核心直觉
如果一个点比另一个点深，两个点不在同一层，就不能直接比较祖先。
第一步先把深的点往上提到同一深度。为了不一步一步跳，我们预处理：
这样任意距离都可以拆成若干个二进制位。例如要上跳 13 层：
就依次跳 2^3、2^2、2^0。
算法步骤
预处理
任选一个根节点，一般取 1。
DFS 整棵树，求出：
depth[u]：节点u的深度。up[u][0]：节点u的父亲。up[u][j]：节点u的2^j级祖先。
转移式：
直觉是：2^j 级祖先 = 先跳 2^{j-1}，再从那个位置继续跳 2^{j-1}。
查询 LCA
查询 lca(a, b)：
- 如果
a比b浅，交换它们，保证a更深。 - 让
a上跳depth[a] - depth[b]层，使两点同深。 - 如果此时
a == b，说明浅点就是 LCA。 - 从大到小枚举
j：- 如果
up[a][j] != up[b][j]，说明还没跳过 LCA，可以同时上跳。 - 如果相同，说明这一步会跳到 LCA 或 LCA 之上，暂时不能跳。
- 如果
- 循环结束时，
a和b停在 LCA 的两个不同儿子子树中，答案是up[a][0]。
算法证明
一、同深不丢答案
假设 a 更深。
LCA 一定是 a 的祖先，也是 b 的祖先，所以 a 到 LCA 的路径长度不少于 b 到 LCA 的路径长度。先把 a 上跳到和 b 同深，只会删除 a 到 LCA 下方的那段路径，不会跳过 LCA。
因此同深后，LCA 仍然是两个点的公共祖先。
二、从大到小同时跳是正确的
同深后，如果 a != b，它们分别在 LCA 的不同分支里。
从大到小枚举 j 时：
- 如果
up[a][j] != up[b][j]，两者跳完仍在 LCA 下方的不同分支，可以安全跳。 - 如果
up[a][j] == up[b][j]，这次跳会把它们汇合到同一个祖先，可能已经到达或越过 LCA，所以不能跳。
循环结束后，已经不能再让两个点保持“不同祖先”地向上跳。此时它们正好在 LCA 的下面一层，所以父亲就是 LCA。
复杂度分析
设树有
- 预处理时间复杂度：
。 - 单次查询时间复杂度：
。 - 空间复杂度：
。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
const int LOG = 20; // 2^20 > 1e6, 按题目规模调整
struct BinaryLCA {
int n;
vector<int> g[MAXN];
int depth[MAXN];
int up[MAXN][LOG + 1]; // up[u][j] 表示 u 的 2^j 级祖先
void init(int n_) {
n = n_;
for (int i = 1; i <= n; ++i) {
g[i].clear();
depth[i] = 0;
for (int j = 0; j <= LOG; ++j) up[i][j] = 0;
}
}
void add_edge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
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) continue;
dfs(v, u);
}
}
void build(int root = 1) {
depth[0] = 0;
dfs(root, 0);
}
int kth_ancestor(int u, int k) const {
for (int j = 0; j <= LOG; ++j) {
if (k & (1 << j)) u = up[u][j];
}
return u;
}
int lca(int a, int b) const {
if (depth[a] < depth[b]) swap(a, b);
a = kth_ancestor(a, depth[a] - depth[b]);
if (a == b) return a;
for (int j = LOG; j >= 0; --j) {
if (up[a][j] != up[b][j]) {
a = up[a][j];
b = up[b][j];
}
}
return up[a][0];
}
int dist(int a, int b) const {
int c = lca(a, b);
return depth[a] + depth[b] - 2 * depth[c];
}
};
测试用例
树结构：
1
/ \
2 3
/ \ / \
4 5 6 7
查询结果：
| 查询 | LCA | 说明 |
|---|---|---|
lca(4, 5) |
2 |
同在 2 的子树 |
lca(4, 6) |
1 |
分别在根的左右子树 |
lca(3, 7) |
3 |
一个点是另一个点的祖先 |
dist(4, 6) |
4 |
路径是 4-2-1-3-6 |
应用分类详解
LCA 的本质是把树上两点路径拆成“向上到公共祖先”的两段。
一、树上路径查询
典型模式： 题目反复询问两点路径上的长度、权值和、最大值或最小值。
识别信号： 多次询问 u 到 v 的路径，路径经过它们的公共祖先。
核心建模： 先找到 lca(u, v)，再把路径拆成 u -> lca 和 v -> lca。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 两点距离 | luogu-P3379 | 距离由两点深度和 LCA 深度计算 |
| 路径最大边 | 次小生成树类问题 | 倍增表中同时维护祖先和路径信息 |
二、祖先关系判断
典型模式： 判断一个点是否在另一个点的子树里，或某个点是否位于路径上。
识别信号： 祖先、后代、子树、路径经过。
核心建模： 用 LCA 或 DFS 序判断包含关系。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 判断祖先 | DFS 序 + LCA | lca(u, v) == u 表示 u 是 v 的祖先 |
| 路径包含 | 距离拆分 | dist(a, x) + dist(x, b) == dist(a, b) |
三、树上差分
典型模式： 多次给树上路径加一，最后统计点或边的贡献。
识别信号： 多条路径、路径覆盖次数、最后统一统计。
核心建模： 对路径两端加贡献，在 LCA 和 LCA 的父亲处抵消，然后 DFS 汇总。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 点差分 | luogu-P3258 | u、v 加，lca 和 fa[lca] 减 |
| 边差分 | 树上路径覆盖 | u、v 加，lca 减两次 |
经典例题
- luogu-P3379 【模板】最近公共祖先：倍增 LCA 标准模板题。
- luogu-P3258 松鼠的新家：LCA 和树上差分结合。
- luogu-P1967 货车运输：最大生成树上用 LCA 查询路径瓶颈。