本课时有配套视频讲解，购买后即可观看（永久有效）

树的欧拉序

一、课上练习

编程练习

（暂无）

二、知识总结

✨ 核心思想

树的欧拉序（Euler Tour）是将树的 DFS 遍历过程完整记录下来的序列：每次进入一个节点时记录它，每次从子节点返回时也记录它。与 DFS 序不同，欧拉序中每个节点会出现多次（度数+1 次），总长度为 2n-1。欧拉序最重要的应用是将 LCA（最近公共祖先）问题转化为 RMQ（区间最值查询）问题。

✨ 算法原理

欧拉序的构造：

在 DFS 过程中：

第一次进入节点 u 时，将 u 加入序列
每次从子节点 v 返回节点 u 时，再将 u 加入序列

对于 n 个节点的树，欧拉序长度为 2n-1。

与 DFS 序的区别：

特性	DFS 序	欧拉序
每个节点出现次数	1 次	多次（度数+1）
序列长度	n	2n-1
主要用途	子树转区间	LCA转RMQ

欧拉序与 LCA 的关系：

设 first[u] 为节点 u 在欧拉序中第一次出现的位置，depth[i] 为欧拉序第 i 个节点的深度。

则 LCA(u, v) = 欧拉序中区间 [first[u], first[v]] 内深度最小的节点。

为什么成立？ 从 u 到 v 在 DFS 中的路径一定经过 LCA(u, v)，而欧拉序中 u 的首次出现到 v 的首次出现之间，记录了从 u 走到 v 的所有经过的节点，其中深度最小的一定是 LCA。

✨ 代码实现

1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<int> adj[MAXN];
7int euler[2 * MAXN]; // 欧拉序列（最长2n-1）
8int depth_e[2 * MAXN]; // 欧拉序中每个位置的深度
9int first_pos[MAXN];   // 每个节点在欧拉序中第一次出现的位置
10int euler_cnt = 0;     // 欧拉序当前长度
11int n;
12
13void dfs(int u, int fa, int d) {
14    // 进入节点u，加入欧拉序
15    euler[++euler_cnt] = u;
16    depth_e[euler_cnt] = d;
17    first_pos[u] = euler_cnt;
18
19    for (int v : adj[u]) {
20        if (v == fa) continue;
21        dfs(v, u, d + 1);
22        // 从子节点v返回u，再次加入欧拉序
23        euler[++euler_cnt] = u;
24        depth_e[euler_cnt] = d;
25    }
26}
27
28int main() {
29    cin >> n;
30    for (int i = 0; i < n - 1; i++) {
31        int u, v;
32        cin >> u >> v;
33        adj[u].push_back(v);
34        adj[v].push_back(u);
35    }
36
37    dfs(1, 0, 0);
38
39    // 输出欧拉序
40    cout << "欧拉序：";
41    for (int i = 1; i <= euler_cnt; i++) {
42        cout << euler[i] << " ";
43    }
44    cout << endl;
45
46    // 输出深度
47    cout << "深度序：";
48    for (int i = 1; i <= euler_cnt; i++) {
49        cout << depth_e[i] << " ";
50    }
51    cout << endl;
52
53    // 输出首次出现位置
54    for (int i = 1; i <= n; i++) {
55        cout << "first[" << i << "] = " << first_pos[i] << endl;
56    }
57
58    return 0;
59}

1#include <iostream>
2#include <vector>
3#include <cmath>
4using namespace std;
5
6const int MAXN = 100005;
7const int LOG = 18; // log2(2*MAXN)
8
9vector<int> adj[MAXN];
10int euler[2 * MAXN];
11int depth_e[2 * MAXN];
12int first_pos[MAXN];
13int euler_cnt = 0;
14int n, q;
15
16// 稀疏表（Sparse Table）用于RMQ
17// sparse[i][j]: 从位置i开始长度为2^j的区间中深度最小的位置
18int sparse[2 * MAXN][LOG];
19
20void dfs(int u, int fa, int d) {
21    euler[++euler_cnt] = u;
22    depth_e[euler_cnt] = d;
23    first_pos[u] = euler_cnt;
24
25    for (int v : adj[u]) {
26        if (v == fa) continue;
27        dfs(v, u, d + 1);
28        euler[++euler_cnt] = u;
29        depth_e[euler_cnt] = d;
30    }
31}
32
33// 构建稀疏表
34void buildSparseTable() {
35    int len = euler_cnt;
36    // 初始化：区间长度为1
37    for (int i = 1; i <= len; i++) {
38        sparse[i][0] = i;
39    }
40
41    // 倍增构建
42    for (int j = 1; (1 << j) <= len; j++) {
43        for (int i = 1; i + (1 << j) - 1 <= len; i++) {
44            int left = sparse[i][j - 1];
45            int right = sparse[i + (1 << (j - 1))][j - 1];
46            // 取深度更小的位置
47            sparse[i][j] = (depth_e[left] <= depth_e[right]) ? left : right;
48        }
49    }
50}
51
52// RMQ查询：返回区间[l,r]中深度最小的位置
53int rmq(int l, int r) {
54    if (l > r) swap(l, r);
55    int k = __lg(r - l + 1); // log2(r-l+1)
56    int left = sparse[l][k];
57    int right = sparse[r - (1 << k) + 1][k];
58    return (depth_e[left] <= depth_e[right]) ? left : right;
59}
60
61// 查询LCA
62int lca(int u, int v) {
63    int l = first_pos[u], r = first_pos[v];
64    int pos = rmq(l, r);
65    return euler[pos]; // 返回LCA节点
66}
67
68int main() {
69    ios::sync_with_stdio(false);
70    cin.tie(nullptr);
71
72    cin >> n >> q;
73    for (int i = 0; i < n - 1; i++) {
74        int u, v;
75        cin >> u >> v;
76        adj[u].push_back(v);
77        adj[v].push_back(u);
78    }
79
80    dfs(1, 0, 0);
81    buildSparseTable();
82
83    // 回答LCA查询
84    while (q--) {
85        int u, v;
86        cin >> u >> v;
87        cout << lca(u, v) << "\n";
88    }
89
90    return 0;
91}

✨ 执行示例

以下面的树为例（以 1 为根）：

DFS 遍历过程：

进入1 → 进入2 → 进入4 → 离开4,回到2 → 进入5 → 离开5,回到2 → 离开2,回到1 → 进入3 → 离开3,回到1

欧拉序：

位置:    1  2  3  4  5  6  7  8  9
欧拉序:  1  2  4  2  5  2  1  3  1
深度:    0  1  2  1  2  1  0  1  0

首次出现位置：

first[1]=1, first[2]=2, first[3]=8, first[4]=3, first[5]=5

查询 LCA(4, 5)：

first[4]=3, first[5]=5
区间 [3, 5] 中的深度序列：2, 1, 2
深度最小值为 1，对应位置 4，euler[4]=2
所以 LCA(4, 5) = 2

查询 LCA(4, 3)：

first[4]=3, first[3]=8
区间 [3, 8] 中的深度序列：2, 1, 2, 1, 0, 1
深度最小值为 0，对应位置 7，euler[7]=1
所以 LCA(4, 3) = 1

✨ 解题步骤详解

建树：读入边信息，构建邻接表
DFS 构建欧拉序：记录每次进入和返回时的节点和深度
记录首次出现位置：first[u] = u 在欧拉序中第一次出现的下标
构建稀疏表：对深度数组预处理 RMQ
回答 LCA 查询：LCA(u,v) = euler[RMQ(first[u], first[v])]

注意事项：

欧拉序长度为 2n-1，数组大小至少开 2n
稀疏表的 LOG 值需要足够大（通常取 18 或 20）
查询时需要处理 first[u] > first[v] 的情况（交换或取 min/max）

✨ 常见错误

欧拉序数组开小：应该至少开 2n 大小，而非 n
忘记在返回父节点时记录：欧拉序要求从子节点返回时也记录当前节点
RMQ 返回的是位置而非值：稀疏表存的是位置，取 LCA 时要用 euler[pos]
first 数组更新错误：只记录第一次出现的位置，不能覆盖
稀疏表构建时的区间长度计算错误：(1 << j) 和 (1 << (j-1)) 不要搞混
查询时 l > r 没有交换：需要保证 l <= r

✨ 算法评价

指标	值
预处理时间	O(n log n)，DFS O(n) + 稀疏表 O(n log n)
单次查询时间	O(1)
空间复杂度	O(n log n)

欧拉序将 LCA 问题优雅地转化为 RMQ 问题，是一种非常经典的算法思想。预处理后可以 O(1) 回答每次 LCA 查询，适合大量查询的场景。与倍增法相比，查询更快但实现稍复杂。