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

树的DFS序

一、课上练习

编程练习

（暂无）

二、知识总结

✨ 核心思想

树的 DFS 序是对树进行深度优先遍历时，记录每个节点的进入时间（in-time）和离开时间（out-time）。利用 DFS 序的一个关键性质——一个节点的子树对应 DFS 序中的一段连续区间——可以将树上的子树操作转化为区间操作，从而利用线段树、树状数组等数据结构高效处理。

✨ 算法原理

DFS 序的定义：

对树进行 DFS 遍历，设全局时间戳 timer：

进入节点 u 时，记录 in[u] = ++timer
离开节点 u 时（所有子节点都已访问完），记录 out[u] = timer

关键性质：

子树区间性：节点 u 的所有子孙的 in 值都在 [in[u], out[u]] 范围内
祖先判断：u 是 v 的祖先当且仅当 in[u] <= in[v] 且 out[u] >= out[v]
不相交性：如果 u 和 v 没有祖先关系，则它们的区间不相交

应用场景：

子树修改/查询：将子树 u 的操作转化为区间 [in[u], out[u]] 上的操作
路径修改/查询：配合 LCA 和差分使用
判断祖先关系：O(1) 判断两个节点是否有祖先关系

✨ 代码实现

1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<int> adj[MAXN]; // 邻接表
7int in_time[MAXN];     // 进入时间
8int out_time[MAXN];    // 离开时间
9int dfn[MAXN];         // DFS序：dfn[时间]=节点编号
10int timer_cnt = 0;
11int n;
12
13// DFS求DFS序
14void dfs(int u, int fa) {
15    in_time[u] = ++timer_cnt; // 记录进入时间
16    dfn[timer_cnt] = u;       // 第timer_cnt个访问的是节点u
17
18    for (int v : adj[u]) {
19        if (v == fa) continue;
20        dfs(v, u);
21    }
22
23    out_time[u] = timer_cnt; // 记录离开时间
24}
25
26int main() {
27    cin >> n;
28    for (int i = 0; i < n - 1; i++) {
29        int u, v;
30        cin >> u >> v;
31        adj[u].push_back(v);
32        adj[v].push_back(u);
33    }
34
35    dfs(1, 0); // 以1为根
36
37    // 输出每个节点的DFS序区间
38    for (int i = 1; i <= n; i++) {
39        cout << "节点 " << i << ": [" << in_time[i]
40             << ", " << out_time[i] << "]" << endl;
41    }
42
43    return 0;
44}

1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<int> adj[MAXN];
7int in_time[MAXN], out_time[MAXN];
8int timer_cnt = 0;
9int n, q;
10int val[MAXN]; // 节点权值
11
12long long bit[MAXN]; // 树状数组
13
14// 树状数组操作
15void update(int pos, long long v) {
16    for (; pos <= n; pos += pos & (-pos))
17        bit[pos] += v;
18}
19
20long long query(int pos) {
21    long long sum = 0;
22    for (; pos > 0; pos -= pos & (-pos))
23        sum += bit[pos];
24    return sum;
25}
26
27// 区间求和 [l, r]
28long long rangeQuery(int l, int r) {
29    return query(r) - query(l - 1);
30}
31
32void dfs(int u, int fa) {
33    in_time[u] = ++timer_cnt;
34    for (int v : adj[u]) {
35        if (v == fa) continue;
36        dfs(v, u);
37    }
38    out_time[u] = timer_cnt;
39}
40
41int main() {
42    ios::sync_with_stdio(false);
43    cin.tie(nullptr);
44
45    cin >> n >> q;
46    for (int i = 1; i <= n; i++) cin >> val[i];
47    for (int i = 0; i < n - 1; i++) {
48        int u, v;
49        cin >> u >> v;
50        adj[u].push_back(v);
51        adj[v].push_back(u);
52    }
53
54    dfs(1, 0);
55
56    // 将节点权值放到DFS序对应的位置
57    for (int i = 1; i <= n; i++) {
58        update(in_time[i], val[i]);
59    }
60
61    while (q--) {
62        int type;
63        cin >> type;
64        if (type == 1) {
65            // 单点修改：将节点u的权值改为x
66            int u;
67            long long x;
68            cin >> u >> x;
69            update(in_time[u], x - val[u]);
70            val[u] = x;
71        } else {
72            // 子树查询：查询节点u的子树权值和
73            int u;
74            cin >> u;
75            long long ans = rangeQuery(in_time[u], out_time[u]);
76            cout << ans << "\n";
77        }
78    }
79
80    return 0;
81}

1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<int> adj[MAXN];
7int in_time[MAXN], out_time[MAXN];
8int timer_cnt = 0;
9
10void dfs(int u, int fa) {
11    in_time[u] = ++timer_cnt;
12    for (int v : adj[u]) {
13        if (v == fa) continue;
14        dfs(v, u);
15    }
16    out_time[u] = timer_cnt;
17}
18
19// O(1)判断u是否是v的祖先
20bool isAncestor(int u, int v) {
21    return in_time[u] <= in_time[v] && out_time[u] >= out_time[v];
22}
23
24int main() {
25    int n;
26    cin >> n;
27    for (int i = 0; i < n - 1; i++) {
28        int u, v;
29        cin >> u >> v;
30        adj[u].push_back(v);
31        adj[v].push_back(u);
32    }
33
34    dfs(1, 0);
35
36    // 查询
37    int u, v;
38    cin >> u >> v;
39    if (isAncestor(u, v)) {
40        cout << u << " 是 " << v << " 的祖先" << endl;
41    } else if (isAncestor(v, u)) {
42        cout << v << " 是 " << u << " 的祖先" << endl;
43    } else {
44        cout << u << " 和 " << v << " 没有祖先关系" << endl;
45    }
46
47    return 0;
48}

✨ 执行示例

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

DFS 遍历顺序（假设按编号从小到大访问子节点）：

1访问1: in[1]=1
2  访问2: in[2]=2
3    访问5: in[5]=3, out[5]=3
4    访问6: in[6]=4, out[6]=4
5  out[2]=4
6  访问3: in[3]=5, out[3]=5
7  访问4: in[4]=6
8    访问7: in[7]=7, out[7]=7
9  out[4]=7
10out[1]=7

DFS 序区间：

1节点1: [1, 7]  → 子树包含所有节点
2节点2: [2, 4]  → 子树包含 {2, 5, 6}
3节点3: [5, 5]  → 子树只有自身
4节点4: [6, 7]  → 子树包含 {4, 7}
5节点5: [3, 3]  → 叶子节点
6节点6: [4, 4]  → 叶子节点
7节点7: [7, 7]  → 叶子节点

验证子树区间性：

节点 2 的子树 = {2, 5, 6}，in 值 = {2, 3, 4}，恰好是区间 [2, 4]
节点 4 的子树 = {4, 7}，in 值 = {6, 7}，恰好是区间 [6, 7]

查询子树权值和示例： 假设 val = [0, 10, 20, 30, 40, 50, 60, 70]（节点 1-7），查询节点 2 的子树权值和 = val[2]+val[5]+val[6] = 20+50+60 = 130，等价于树状数组在区间 [2,4] 上的和。

✨ 解题步骤详解

建树：读入边信息，构建邻接表
确定根节点：通常题目指定根，或默认为节点 1
DFS 求序：进入时记录 in_time，离开时记录 out_time
将节点值映射到 DFS 序：a[in_time[u]] = val[u]
用数据结构维护区间：根据操作选择线段树或树状数组
子树操作转区间操作：[in_time[u], out_time[u]]

✨ 常见错误

in_time 和 out_time 搞混：in 在进入时赋值，out 在所有子节点访问完后赋值
DFS 序数组下标错误：DFS 序从 1 开始，注意数组大小
忘记将节点值映射到 DFS 序位置：直接用节点编号而非 DFS 序编号操作数据结构
非根节点调用 DFS：DFS 应从根节点开始
子树区间写错：区间是 [in[u], out[u]]，不是 [in[u], in[u]+sz[u]-1]（虽然等价，但容易写错 sz）
递归栈溢出：节点数很大时需要手动扩栈或改为非递归

✨ 算法评价

指标	值
预处理时间	O(n)，一次 DFS
空间复杂度	O(n)
祖先判断	O(1)
子树查询/修改	取决于配合的数据结构

DFS 序是树上问题的重要工具，它架起了"树结构"与"线性结构"之间的桥梁。配合线段树、树状数组等数据结构，可以高效解决子树修改/查询、路径修改/查询等问题。