本课时有配套视频讲解，购买后即可观看（永久有效）
欧拉序求最近公共祖先
一、课上练习
编程练习
二、知识总结
✨ 核心思想
利用欧拉序将 LCA（最近公共祖先）问题转化为 RMQ（区间最值查询）问题，通过稀疏表（Sparse Table）实现 O(n log n) 预处理、O(1) 查询的高效算法。这是处理大量 LCA 查询时的最优方案之一。
✨ 算法原理
LCA 转 RMQ 的完整推导：
给定有根树，对于任意两个节点 u 和 v，它们的 LCA 具有如下性质：从 u 到 v 在树上的路径必然经过 LCA(u, v)，且 LCA(u, v) 是路径上深度最小的节点。
转化步骤：
- 构造欧拉序：DFS 遍历树，进入和返回节点时都记录，得到长度为 2n-1 的序列
- 记录深度：同时记录欧拉序中每个位置对应的节点深度
- 记录首次出现：
first[u]为节点 u 在欧拉序中第一次出现的下标 - LCA 查询转 RMQ：LCA(u, v) 就是欧拉序中
[first[u], first[v]]区间内深度最小的节点
稀疏表（Sparse Table）：
稀疏表是处理静态 RMQ 问题的最优数据结构：
- 预处理：
st[i][j]表示从位置 i 开始长度为 2^j 的区间中的最小值位置 - 递推：
st[i][j] = better(st[i][j-1], st[i + 2^(j-1)][j-1]) - 查询：利用两个可能重叠的区间覆盖整个查询区间，O(1) 完成
✨ 代码实现
1#include <iostream>
2#include <vector>
3#include <cstring>
4using namespace std;
5
6const int MAXN = 500005; // 最大节点数
7const int MAXM = 1000005; // 欧拉序最大长度 (2*MAXN)
8const int LOG = 21; // log2(MAXM) + 1
9
10// 树的存储
11vector<int> adj[MAXN];
12int n, q;
13
14// 欧拉序相关
15int euler[MAXM]; // 欧拉序列
16int depth_e[MAXM]; // 欧拉序中对应深度
17int first_pos[MAXN]; // 每个节点首次出现位置
18int euler_len = 0; // 欧拉序长度
19
20// 稀疏表
21int st[MAXM][LOG]; // st[i][j]：从i开始2^j长度区间内深度最小的位置
22int lg[MAXM]; // 预处理log2
23
24// DFS构建欧拉序
25void dfs(int u, int fa, int d) {
26 // 进入节点u
27 euler_len++;
28 euler[euler_len] = u;
29 depth_e[euler_len] = d;
30 first_pos[u] = euler_len;
31
32 for (int v : adj[u]) {
33 if (v == fa) continue;
34 dfs(v, u, d + 1);
35 // 从v返回u
36 euler_len++;
37 euler[euler_len] = u;
38 depth_e[euler_len] = d;
39 }
40}
41
42// 预处理log2值
43void preLog() {
44 lg[1] = 0;
45 for (int i = 2; i <= euler_len; i++) {
46 lg[i] = lg[i / 2] + 1;
47 }
48}
49
50// 构建稀疏表
51void buildST() {
52 preLog();
53
54 // 初始化：长度为1的区间
55 for (int i = 1; i <= euler_len; i++) {
56 st[i][0] = i;
57 }
58
59 // 倍增构建
60 for (int j = 1; j <= lg[euler_len]; j++) {
61 for (int i = 1; i + (1 << j) - 1 <= euler_len; i++) {
62 int left = st[i][j - 1];
63 int right = st[i + (1 << (j - 1))][j - 1];
64 st[i][j] = (depth_e[left] <= depth_e[right]) ? left : right;
65 }
66 }
67}
68
69// RMQ查询：区间[l,r]中深度最小的位置
70int queryRMQ(int l, int r) {
71 if (l > r) swap(l, r);
72 int k = lg[r - l + 1];
73 int left = st[l][k];
74 int right = st[r - (1 << k) + 1][k];
75 return (depth_e[left] <= depth_e[right]) ? left : right;
76}
77
78// LCA查询
79int lca(int u, int v) {
80 int l = first_pos[u], r = first_pos[v];
81 int pos = queryRMQ(l, r);
82 return euler[pos];
83}
84
85// 求树上两点距离（需要节点深度）
86int dep[MAXN];
87void calcDepth(int u, int fa, int d) {
88 dep[u] = d;
89 for (int v : adj[u]) {
90 if (v == fa) continue;
91 calcDepth(v, u, d + 1);
92 }
93}
94
95int dist(int u, int v) {
96 int w = lca(u, v);
97 return dep[u] + dep[v] - 2 * dep[w];
98}
99
100int main() {
101 ios::sync_with_stdio(false);
102 cin.tie(nullptr);
103
104 cin >> n >> q;
105 for (int i = 0; i < n - 1; i++) {
106 int u, v;
107 cin >> u >> v;
108 adj[u].push_back(v);
109 adj[v].push_back(u);
110 }
111
112 // 预处理
113 dfs(1, 0, 0); // 构建欧拉序
114 buildST(); // 构建稀疏表
115 calcDepth(1, 0, 0); // 求各节点深度
116
117 // 回答查询
118 while (q--) {
119 int u, v;
120 cin >> u >> v;
121 int w = lca(u, v);
122 cout << w << "\n";
123 }
124
125 return 0;
126}1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 500005;
6const int MAXM = 1000005;
7const int LOG = 21;
8
9vector<pair<int,int>> adj[MAXN]; // (终点, 边权)
10int euler[MAXM], depth_e[MAXM], first_pos[MAXN];
11int st[MAXM][LOG], lg[MAXM];
12int euler_len = 0;
13long long dis[MAXN]; // 到根的距离
14int n, q;
15
16void dfs(int u, int fa, int d, long long w) {
17 depth_e[++euler_len] = d;
18 euler[euler_len] = u;
19 first_pos[u] = euler_len;
20 dis[u] = w;
21
22 for (auto& e : adj[u]) {
23 int v = e.first;
24 int wt = e.second;
25 if (v == fa) continue;
26 dfs(v, u, d + 1, w + wt);
27 depth_e[++euler_len] = d;
28 euler[euler_len] = u;
29 }
30}
31
32void build() {
33 lg[1] = 0;
34 for (int i = 2; i <= euler_len; i++) lg[i] = lg[i/2] + 1;
35 for (int i = 1; i <= euler_len; i++) st[i][0] = i;
36 for (int j = 1; j <= lg[euler_len]; j++)
37 for (int i = 1; i + (1<<j) - 1 <= euler_len; i++) {
38 int l = st[i][j-1], r = st[i+(1<<(j-1))][j-1];
39 st[i][j] = (depth_e[l] <= depth_e[r]) ? l : r;
40 }
41}
42
43int lca(int u, int v) {
44 int l = first_pos[u], r = first_pos[v];
45 if (l > r) swap(l, r);
46 int k = lg[r-l+1];
47 int a = st[l][k], b = st[r-(1<<k)+1][k];
48 return euler[(depth_e[a] <= depth_e[b]) ? a : b];
49}
50
51// 带权树上两点距离
52long long treeDist(int u, int v) {
53 return dis[u] + dis[v] - 2 * dis[lca(u, v)];
54}
55
56int main() {
57 ios::sync_with_stdio(false);
58 cin.tie(nullptr);
59
60 cin >> n >> q;
61 for (int i = 0; i < n - 1; i++) {
62 int u, v, w;
63 cin >> u >> v >> w;
64 adj[u].push_back({v, w});
65 adj[v].push_back({u, w});
66 }
67
68 dfs(1, 0, 0, 0);
69 build();
70
71 while (q--) {
72 int u, v;
73 cin >> u >> v;
74 cout << treeDist(u, v) << "\n";
75 }
76 return 0;
77}✨ 执行示例
以下面的树为例：
1
/ | \
2 3 4
/| |
5 6 7构建欧拉序（DFS 从 1 开始）：
1进入1(深度0) → 进入2(深度1) → 进入5(深度2) → 回到2(深度1)
2→ 进入6(深度2) → 回到2(深度1) → 回到1(深度0)
3→ 进入3(深度1) → 回到1(深度0)
4→ 进入4(深度1) → 进入7(深度2) → 回到4(深度1) → 回到1(深度0)
5
6位置: 1 2 3 4 5 6 7 8 9 10 11 12 13
7欧拉序: 1 2 5 2 6 2 1 3 1 4 7 4 1
8深度: 0 1 2 1 2 1 0 1 0 1 2 1 0
9
10first_pos: first[1]=1, first[2]=2, first[3]=8,
11 first[4]=10, first[5]=3, first[6]=5, first[7]=11查询 LCA(5, 6)：
first[5]=3, first[6]=5
区间 [3, 5] 的深度: 2, 1, 2
最小深度=1，位置=4，euler[4]=2
LCA(5, 6) = 2查询 LCA(6, 7)：
first[6]=5, first[7]=11
区间 [5, 11] 的深度: 2, 1, 0, 1, 0, 1, 2
最小深度=0，位置=7(或9)，euler[7]=1
LCA(6, 7) = 1稀疏表查询示例（查询 [5, 11]）：
区间长度 = 11-5+1 = 7
k = lg[7] = 2, 2^k = 4
查询 st[5][2]（覆盖[5,8]）和 st[8][2]（覆盖[8,11]）
两段取深度更小的位置 → 返回深度0的位置✨ 解题步骤详解
- 读入树：建立邻接表存储
- DFS 构建欧拉序：记录 euler、depth_e、first_pos 三个数组
- 预处理 log 值：避免每次查询时计算
- 构建稀疏表：对 depth_e 数组建立 ST 表
- 回答查询：
- LCA(u, v)：取
euler[queryRMQ(first[u], first[v])] - 距离(u, v)：
dep[u] + dep[v] - 2 * dep[LCA(u,v)]
- LCA(u, v)：取
时间分析：
- 预处理：DFS O(n) + ST 表 O(n log n) = O(n log n)
- 单次查询：O(1)
- q 次查询总时间：O(n log n + q)
✨ 常见错误
- 数组大小不够：欧拉序长度为 2n-1，稀疏表也要开 2n 大小
- LOG 值太小：需要 LOG >= log2(2n) + 1
- lg 数组预处理范围不够：必须预处理到 euler_len
- 稀疏表存的是位置而非深度值：查询返回的是位置，要通过 euler 数组获取节点
- first_pos 被覆盖：只记录首次出现，后续出现不要更新
- 查询区间左右端没有排序：需要保证
l <= r - 递归栈溢出：n 较大时（>1e5），需要手动扩栈或改为迭代
✨ 算法评价
| 指标 | 值 |
|---|---|
| 预处理时间 | O(n log n) |
| 单次查询 | O(1) |
| 空间复杂度 | O(n log n) |
| 实现难度 | 中等 |
与其他 LCA 算法的比较：
| 算法 | 预处理 | 查询 | 空间 | 特点 |
|---|---|---|---|---|
| 欧拉序+ST表 | O(n log n) | O(1) | O(n log n) | 查询最快 |
| 倍增法 | O(n log n) | O(log n) | O(n log n) | 实现简单，用途广 |
| Tarjan离线 | O(n + q) | O(1)（离线） | O(n) | 必须离线处理 |
| 树链剖分 | O(n) | O(log n) | O(n) | 可维护路径信息 |
欧拉序+ST 表方案在需要大量在线 LCA 查询时表现最佳，是竞赛中的常用技巧。
三、课后练习
编程练习
- 祖孙询问：L50009