本课时有配套视频讲解，购买后即可观看（永久有效）
倍增法求最近公共祖先
一、课上练习
编程练习
- 最近公共祖先（倍增法）：L49924
二、知识总结
✨ 核心思想
倍增法（Binary Lifting）求最近公共祖先（LCA）的核心思想是：预处理每个节点向上跳 2^k 步到达的祖先，查询时两个节点同步向上跳，以 O(log n) 的时间找到 LCA。倍增法实现简单、适用性广，是竞赛中最常用的 LCA 算法。
✨ 算法原理
预处理：
定义 fa[u][k] 表示节点 u 向上跳 2^k 步到达的祖先。
递推关系：
fa[u][0]= u 的父节点fa[u][k] = fa[fa[u][k-1]][k-1]（先跳 2^(k-1) 步，再跳 2^(k-1) 步）
查询 LCA(u, v)：
- 对齐深度：将深度较大的节点向上跳到与另一个节点同深度
- 同步上跳：两个节点同步向上跳，找到 LCA
详细步骤：
- 假设
dep[u] >= dep[v]（否则交换） - 将 u 向上跳
dep[u] - dep[v]步（利用二进制分解） - 如果此时 u == v，返回 u
- 从大到小枚举 k，如果
fa[u][k] != fa[v][k]，则同时上跳 - 最终
fa[u][0]就是 LCA
为什么从大到小枚举？ 贪心策略：优先尝试跳大步，跳不了再尝试小步。最终 u 和 v 会停在 LCA 的正下方。
✨ 代码实现
1#include <iostream>
2#include <vector>
3#include <cstring>
4using namespace std;
5
6const int MAXN = 500005;
7const int LOG = 20; // log2(500000) 约等于 19
8
9vector<int> adj[MAXN];
10int fa[MAXN][LOG]; // fa[u][k]: u向上跳2^k步的祖先
11int dep[MAXN]; // 节点深度
12int n, q;
13
14// DFS预处理深度和fa数组
15void dfs(int u, int father, int d) {
16 dep[u] = d;
17 fa[u][0] = father;
18
19 // 倍增预处理
20 for (int k = 1; k < LOG; k++) {
21 fa[u][k] = fa[fa[u][k - 1]][k - 1];
22 }
23
24 for (int v : adj[u]) {
25 if (v == father) continue;
26 dfs(v, u, d + 1);
27 }
28}
29
30// 查询LCA
31int lca(int u, int v) {
32 // 保证u是更深的节点
33 if (dep[u] < dep[v]) swap(u, v);
34
35 // 第一步：将u上跳到与v同深度
36 int diff = dep[u] - dep[v];
37 for (int k = 0; k < LOG; k++) {
38 if ((diff >> k) & 1) { // diff的第k位为1
39 u = fa[u][k]; // u上跳2^k步
40 }
41 }
42
43 // 如果此时u==v，v就是LCA
44 if (u == v) return u;
45
46 // 第二步：u和v同步上跳
47 for (int k = LOG - 1; k >= 0; k--) {
48 if (fa[u][k] != fa[v][k]) {
49 u = fa[u][k];
50 v = fa[v][k];
51 }
52 }
53
54 // 此时u和v的父节点就是LCA
55 return fa[u][0];
56}
57
58int main() {
59 ios::sync_with_stdio(false);
60 cin.tie(nullptr);
61
62 cin >> n >> q;
63 // 读入n-1条边
64 for (int i = 0; i < n - 1; i++) {
65 int u, v;
66 cin >> u >> v;
67 adj[u].push_back(v);
68 adj[v].push_back(u);
69 }
70
71 // 以1为根，预处理
72 memset(fa, 0, sizeof(fa));
73 dfs(1, 0, 0);
74
75 // 回答查询
76 while (q--) {
77 int u, v;
78 cin >> u >> v;
79 cout << lca(u, v) << "\n";
80 }
81
82 return 0;
83}1#include <iostream>
2#include <vector>
3#include <cstring>
4using namespace std;
5
6const int MAXN = 500005;
7const int LOG = 20;
8
9vector<pair<int,int>> adj[MAXN]; // (终点, 边权)
10int fa[MAXN][LOG];
11int dep[MAXN];
12long long dis[MAXN]; // 到根的距离
13int maxw[MAXN][LOG]; // 路径上的最大边权
14int n, q;
15
16void dfs(int u, int father, int d, long long w) {
17 dep[u] = d;
18 dis[u] = w;
19 fa[u][0] = father;
20
21 for (int k = 1; k < LOG; k++) {
22 fa[u][k] = fa[fa[u][k-1]][k-1];
23 // 合并路径最大边权
24 maxw[u][k] = max(maxw[u][k-1], maxw[fa[u][k-1]][k-1]);
25 }
26
27 for (auto& e : adj[u]) {
28 int v = e.first, wt = e.second;
29 if (v == father) continue;
30 maxw[v][0] = wt; // v到父节点的边权
31 dfs(v, u, d + 1, w + wt);
32 }
33}
34
35int lca(int u, int v) {
36 if (dep[u] < dep[v]) swap(u, v);
37 int diff = dep[u] - dep[v];
38 for (int k = 0; k < LOG; k++)
39 if ((diff >> k) & 1) u = fa[u][k];
40 if (u == v) return u;
41 for (int k = LOG - 1; k >= 0; k--)
42 if (fa[u][k] != fa[v][k]) {
43 u = fa[u][k];
44 v = fa[v][k];
45 }
46 return fa[u][0];
47}
48
49// 两点距离
50long long treeDist(int u, int v) {
51 return dis[u] + dis[v] - 2 * dis[lca(u, v)];
52}
53
54// 路径上最大边权（需要在上跳过程中维护）
55int pathMax(int u, int v) {
56 int res = 0;
57 if (dep[u] < dep[v]) swap(u, v);
58
59 int diff = dep[u] - dep[v];
60 for (int k = 0; k < LOG; k++) {
61 if ((diff >> k) & 1) {
62 res = max(res, maxw[u][k]);
63 u = fa[u][k];
64 }
65 }
66
67 if (u == v) return res;
68
69 for (int k = LOG - 1; k >= 0; k--) {
70 if (fa[u][k] != fa[v][k]) {
71 res = max(res, max(maxw[u][k], maxw[v][k]));
72 u = fa[u][k];
73 v = fa[v][k];
74 }
75 }
76 res = max(res, max(maxw[u][0], maxw[v][0]));
77 return res;
78}
79
80int main() {
81 ios::sync_with_stdio(false);
82 cin.tie(nullptr);
83
84 cin >> n >> q;
85 for (int i = 0; i < n - 1; i++) {
86 int u, v, w;
87 cin >> u >> v >> w;
88 adj[u].push_back({v, w});
89 adj[v].push_back({u, w});
90 }
91
92 memset(fa, 0, sizeof(fa));
93 memset(maxw, 0, sizeof(maxw));
94 dfs(1, 0, 0, 0);
95
96 while (q--) {
97 int op, u, v;
98 cin >> op >> u >> v;
99 if (op == 1) {
100 cout << treeDist(u, v) << "\n";
101 } else {
102 cout << pathMax(u, v) << "\n";
103 }
104 }
105 return 0;
106}✨ 执行示例
以下面的树为例（以 1 为根）：
1 1 (深度0)
2 / \
3 2 3 (深度1)
4 / \ \
5 4 5 6 (深度2)
6 /
7 7 (深度3)预处理 fa 数组：
1fa[u][0]（父节点）:
2 fa[1][0]=0, fa[2][0]=1, fa[3][0]=1, fa[4][0]=2
3 fa[5][0]=2, fa[6][0]=3, fa[7][0]=4
4
5fa[u][1]（向上跳2步）:
6 fa[2][1]=fa[fa[2][0]][0]=fa[1][0]=0
7 fa[4][1]=fa[fa[4][0]][0]=fa[2][0]=1
8 fa[7][1]=fa[fa[7][0]][0]=fa[4][0]=2
9
10fa[u][2]（向上跳4步）:
11 fa[7][2]=fa[fa[7][1]][1]=fa[2][1]=0查询 LCA(7, 6)：
1dep[7]=3, dep[6]=2
2差值 diff = 3 - 2 = 1 (二进制: 1)
3
4步骤1：将7上跳1步
5 k=0: diff的第0位为1，u = fa[7][0] = 4
6 现在 u=4, dep[4]=2, v=6, dep[6]=2 → 同深度
7
8步骤2：u=4, v=6, 不相等
9 k=1: fa[4][1]=1, fa[6][1]=1 → 相等，不跳
10 k=0: fa[4][0]=2, fa[6][0]=3 → 不等，跳！
11 u = fa[4][0] = 2
12 v = fa[6][0] = 3
13
14步骤3：返回 fa[2][0] = 1
15
16LCA(7, 6) = 1查询 LCA(7, 5)：
1dep[7]=3, dep[5]=2, diff=1
2将7上跳1步: u = fa[7][0] = 4
3
4u=4, v=5
5k=0: fa[4][0]=2, fa[5][0]=2 → 相等，不跳
6
7返回 fa[4][0] = 2
8
9LCA(7, 5) = 2✨ 解题步骤详解
- 建树：读入边，构建邻接表
- DFS 预处理：一次 DFS 计算 dep 和 fa 数组
- 倍增预处理：
fa[u][k] = fa[fa[u][k-1]][k-1] - 查询时对齐深度：利用二进制分解上跳
- 同步上跳找 LCA：从大到小贪心
实现要点：
- LOG 的值取 ceil(log2(n)) + 1，通常取 20 足够（2^20 > 10^6）
fa[root][k] = 0对所有 k 成立（跳出树外到虚拟节点 0）- 对齐深度时用位运算拆分深度差
✨ 常见错误
- LOG 值太小：导致预处理不完整，查询出错
- fa 数组初始化错误：根节点的父亲应为 0（或 -1），所有
fa[0][k]=0 - 对齐深度时上跳方向搞反：应该是深的节点上跳，不是浅的
- 同步上跳时用从小到大的顺序：必须从大到小，否则可能跳过 LCA
- 忘记处理 u==v 的特殊情况：对齐深度后如果相等，直接返回
- 路径信息查询时漏掉最后一步：同步上跳结束后，u 和 v 到 LCA 还各有一步
✨ 算法评价
| 指标 | 值 |
|---|---|
| 预处理时间 | O(n log n) |
| 单次查询时间 | O(log n) |
| 空间复杂度 | O(n log n) |
| 实现难度 | 较低 |
倍增法的优势：
- 实现简单，代码短
- 容易扩展：可以在上跳过程中维护路径信息（最大值、最小值、和等）
- 在线算法，支持动态查询
- 是学习树链剖分等高级算法的基础
与欧拉序+ST 表的比较：
- 欧拉序方案查询 O(1) 更快，但实现更复杂
- 倍增法更灵活，可以方便地维护路径信息
- 竞赛中倍增法使用更普遍
三、课后练习
编程练习
- Dis：L49926