DFS 序

一句话算法

DFS 序记录每个点进入 DFS 的时间，使一棵子树变成数组上的一个连续区间。

问题模型

给定一棵以 1 为根的树，需要快速处理子树相关问题，例如：

• 判断 u 是否是 v 的祖先；
• 查询某个子树内所有点的信息；
• 对某个子树整体修改；
• 把树上问题转成数组区间问题。

DFS 序为每个点记录两个值：

• in[u]：第一次进入点 u 的时间；
• out[u]：离开 u 的子树时，已经访问到的最大时间。

核心直觉

DFS 进入一个点后，会把它的所有子节点、孙子节点全部访问完，才会回到父亲。

因此，点 u 的整棵子树在访问顺序中一定连续：

这个性质让“子树查询”变成普通数组区间查询。

算法步骤

1. 建树。
2. 从根节点开始 DFS。
3. 进入点 u 时：
   • in[u] = ++timer；
   • order[timer] = u。
4. 递归访问所有未访问儿子。
5. 儿子全部访问完后：
   • out[u] = timer。
6. 点 u 的子树对应 DFS 序区间 [in[u], out[u]]。

祖先判断：

u 是 v 的祖先 <=> in[u] <= in[v] 且 out[v] <= out[u]

算法证明

关键不变量： DFS 在返回 u 的父亲之前，一定已经访问完 u 的整棵子树。

1. 进入 u 时，u 第一个被写入序列，所以子树区间左端是 in[u]。
2. DFS 会递归访问 u 的每个儿子；每个儿子的子树也会在返回前完整访问。
3. 在所有儿子返回之前，DFS 不会访问 u 子树外的点。
4. 因此，从 in[u] 到 out[u] 的所有时间点，恰好对应 u 子树中的点。

所以子树与 DFS 序连续区间一一对应。

复杂度分析

预处理 DFS 序需要访问每个点和每条边一次，时间复杂度为 $O(n)$。

空间复杂度为 $O(n)$。

递归 DFS 在链状树上递归深度为 $O(n)$，如果数据很大，需要注意栈空间。

代码实现

        
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

        #include <bits/stdc++.h>
using namespace std;

struct DFSOrder {
    int n;
    int timer = 0;
    vector<vector<int>> tree;
    vector<int> in, out, parent, depth, order;

    explicit DFSOrder(int n)
        : n(n),
          tree(n + 1),
          in(n + 1),
          out(n + 1),
          parent(n + 1),
          depth(n + 1),
          order(n + 1) {}

    void add_edge(int u, int v) {
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    void dfs(int u, int fa) {
        parent[u] = fa;
        depth[u] = depth[fa] + 1;
        in[u] = ++timer;
        order[timer] = u;

        for (int v : tree[u]) {
            if (v == fa) continue;
            dfs(v, u);
        }

        out[u] = timer;
    }

    bool is_ancestor(int u, int v) const {
        return in[u] <= in[v] && out[v] <= out[u];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    DFSOrder solver(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        solver.add_edge(u, v);
    }

    solver.dfs(1, 0);

    for (int u = 1; u <= n; u++) {
        cout << u << ": " << solver.in[u] << ' ' << solver.out[u] << '\n';
    }

    return 0;
}
    

测试用例

输入：

5
1 2
1 3
2 4
2 5

一种输出：

1: 1 5
2: 2 4
3: 5 5
4: 3 3
5: 4 4

解释：点 2 的子树是 {2,4,5}，对应连续区间 [2,4]。

应用分类详解

DFS 序的本质是把树上的子树结构压平成数组区间。

一、子树查询

典型模式： 查询某个节点子树内的点权和、最大值、颜色数量。

识别信号： 出现“以 u 为根的子树”“子树内所有节点”。

核心建模： 子树转成 [in[u],out[u]]，再用树状数组或线段树维护。

二、祖先关系判断

典型模式： 判断一个点是否在另一个点的子树中。

识别信号： 出现“祖先”“后代”“是否属于某个子树”。

核心建模： 用 in/out 区间包含关系判断祖先。

三、树链和子树混合问题

典型模式： 树链修改、子树查询、单点查询之间相互转化。

识别信号： 同时出现“路径”和“子树”，需要用差分或树状数组维护贡献。

核心建模： 把对子树的贡献转成 DFS 序区间上的加减。

经典例题

1. luogu-P3258

树上路径经过次数统计。先用 LCA 做树上差分，再用 DFS 汇总子树贡献。

2. 子树点权和

把每个点权放到 in[u] 位置，子树和就是数组区间 [in[u],out[u]] 的和。

3. 祖先判断

利用 in[u] <= in[v] && out[v] <= out[u] 可以 $O(1)$ 判断 u 是否为 v 的祖先。

参考

• DFS 遍历
• 树状数组
• 线段树