我的算法书 - DFS 序

一句话算法

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

问题模型

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

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

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

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

核心直觉

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

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

[in(u),out(u)]

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

算法步骤

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

祖先判断：

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

算法证明

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

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

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

复杂度分析

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

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

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

代码实现

C++

cpp

        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;
}

Python

python

        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
65

        # 树的 DFS 序：in_[u] / out[u] 是进入、离开 u 的时间戳，子树 u 恰好占时间戳区间 [in_[u], out[u]]。
# 1 下标：节点编号 1..n，dfs(u, fa) 里 fa = 0 表示根的父亲，depth[0] = 0。
# 判祖先：u 是 v 的祖先 <=> in_[u] <= in_[v] 且 out[v] <= out[u]。
# 树深最坏 n（1e5+），dfs 用显式栈迭代；C++ 字段名 in 在 Python 是关键字，故写作 in_。


class DFSOrder:
    """欧拉序（时间戳）：order[timer] 是第 timer 个被访问的节点。"""

    n: int
    timer: int
    tree: list[list[int]]
    in_: list[int]
    out: list[int]
    parent: list[int]
    depth: list[int]
    order: list[int]

    def __init__(self, n: int) -> None:
        self.n = n
        self.timer = 0
        # 邻接表按节点编号 1..n 开，tree[u] 直接放 u 的邻居。
        self.tree = [[] for _ in range(n + 1)]
        self.in_ = [0] * (n + 1)
        self.out = [0] * (n + 1)
        self.parent = [0] * (n + 1)
        self.depth = [0] * (n + 1)
        self.order = [0] * (n + 1)

    def add_edge(self, u: int, v: int) -> None:
        self.tree[u].append(v)
        self.tree[v].append(u)

    def dfs(self, u: int, fa: int) -> None:
        """从 u 出发遍历，fa 是父亲（0 表示无）。迭代模拟递归，避免深树爆栈。"""
        # 栈元素 (节点, 父亲, 下一条待处理的邻边下标)：下标 0 兼作“尚未进入”的标记。
        stack: list[tuple[int, int, int]] = [(u, fa, 0)]
        while stack:
            node, father, edge_index = stack.pop()
            if edge_index == 0:
                # 第一次进入 node：记父亲、深度、进入时间戳，等价于递归版的前几行。
                self.parent[node] = father
                self.depth[node] = self.depth[father] + 1
                self.timer += 1
                self.in_[node] = self.timer
                self.order[self.timer] = node

            neighbors = self.tree[node]
            advanced = False
            for i in range(edge_index, len(neighbors)):
                v = neighbors[i]
                if v == father:
                    continue
                # 先把“自己从 i + 1 继续”压回去，再压儿子，保证儿子先被处理完。
                stack.append((node, father, i + 1))
                stack.append((v, node, 0))
                advanced = True
                break

            if not advanced:
                # 邻边处理完说明子树已全部访问，当前 timer 就是子树的最后一个时间戳。
                self.out[node] = self.timer

    def is_ancestor(self, u: int, v: int) -> bool:
        return self.in_[u] <= self.in_[v] and self.out[v] <= self.out[u]

测试用例

输入：

一种输出：

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

应用分类详解

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

一、子树查询

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

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

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

应用场景	经典题目	核心思路
子树点权和	子树查询类题	DFS 序 + 树状数组区间查询
子树修改	子树加值类题	DFS 序 + 线段树区间修改

二、祖先关系判断

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

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

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

应用场景	经典题目	核心思路
LCA 辅助判断	倍增 LCA 类题	祖先区间包含判断
子树过滤	树上统计题	判断点是否落在某个子树区间

三、树链和子树混合问题

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

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

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

应用场景	经典题目	核心思路
松鼠的新家	luogu-P3258	树上差分统计路径经过次数
子树贡献统计	树上差分类题	区间加、单点查或单点加、区间查

经典例题

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 遍历
树状数组
线段树