DFS 序

一句话算法

进入时记左端点，退出时记右端点：子树从树上的一段，变成数组上的一段。

问题模型

给定一棵 $n$ 个点的有根树（根记作 $root$），需要支持下面几类操作中的一种或几种：

• 子树整体操作：查询子树内的权值和/最大值，或给整棵子树加一个值；
• 祖先判定：快速回答 $u$ 是不是 $v$ 的祖先；
• 路径与子树互化：把“路径修改”变成“子树上的加减”，或者反过来；
• 给出一个线性顺序：让离线算法（排序、扫描线、分块、虚树）可以按这个顺序处理树上的点。

难点在于树不是线性的：一个点和它的子树在编号上毫无规律。DFS 序的做法是重新编号，给每个点记两个时间戳：

• $in_u$：第一次进入点 $u$ 的时刻（用 $1 \sim n$ 依次编号）；
• $out_u$：$u$ 的子树全部访问完、即将离开 $u$ 的时刻，取此时已经用掉的最大编号。

再顺手把点按进入时间排成一排，记 $order[i]$ 为第 $i$ 个被访问的点。这对数组就是本文所有性质的基础。

核心直觉

DFS 只有一个动作：往深处走，走不动再退回。

所以一旦进入点 $u$，在把 $u$ 的每一个后代都走完之前，程序不会离开 $u$，也就不会去碰 $u$ 子树以外的地方。这段时间里计数器只会因为 $u$ 子树里的点而增加。于是：

也就是说，树上的“子树”这种递归结构，在时间轴上是一段连续区间。下图把同一棵树的两种视角并排画了出来。

图中蓝色的四个点是 $2$ 的子树，它们在下方序列里是一整段，右边界正好是 $out(2)=5$。请特别注意：中间没有插进任何不属于子树 $2$ 的点，这正是 DFS 序能用的唯一原因。

三种序列要先分清

“DFS 序”这个词在题解里常常混着用，实际操作时却是四类不同的东西，长度都不一样：

以本文的样例树为例，四种序列分别是：

算法步骤

1. 用邻接表存下 $n-1$ 条无向边，从 $root$ 开始 DFS，父亲用参数传下去，避免走回边。
2. 进入 $u$：in[u] = ++timer，order[timer] = u，sz[u] = 1。
3. 递归每个儿子 $v$：先记 dep[v] = dep[u] + 1，递归完后 sz[u] += sz[v]。
4. 退出 $u$：out[u] = timer。此时 timer 正好是 $in_u + sz_u - 1$，两种写法都常见。
5. 需要欧拉序时，在第 3 步每次从儿子返回后再写一次 $u$。

递归版一眼就能看懂，但树退化成链时递归深度是 $n$。$n \geqslant 10^5$ 时要么开大栈（ulimit -s unlimited），要么改成显式栈：

        
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

        // 迭代 DFS：栈里放 (点, 父亲, 下一条待处理的邻边下标)
void dfs_iter(int root) {
    vector<tuple<int, int, int>> st;
    st.emplace_back(root, 0, 0);
    while (!st.empty()) {
        auto [u, fa, idx] = st.back();
        if (idx == 0) {              // 第一次弹到 u：等同于递归版的“进入”
            in[u] = ++timer;
            order[timer] = u;
            sz[u] = 1;
        }
        bool advanced = false;
        while (idx < (int)tree[u].size()) {
            int v = tree[u][idx++];
            if (v == fa) continue;
            st.back() = make_tuple(u, fa, idx);  // 记住自己处理到哪条边
            dep[v] = dep[u] + 1;
            st.emplace_back(v, u, 0);
            advanced = true;
            break;
        }
        if (!advanced) {             // 邻边走完：退出的时刻
            out[u] = timer;
            st.pop_back();
            if (!st.empty()) sz[get<0>(st.back())] += sz[u];  // 把子树大小交回父亲
        }
    }
}
    

迭代版要记住两件事：idx 兼作“是否已经进入过”的标记，sz 要在弹出时结算给父亲。

性质

下面以一整棵以 $1$ 为根、$in/out/sz/dep/order$ 都已经算好的树为前提。所有性质都来自同一条事实：离开 $u$ 之前，DFS 不会访问 $u$ 子树以外的点。

P1 子树是连续区间

P2 区间长度就是子树大小

所以只存 $in, out$ 两个数组，就能同时得到子树大小；反过来，如果只存了 $in$ 和 $sz$，也能算出 $out_u = in_u + sz_u - 1$。

P3 祖孙关系就是区间包含

等价的写法是两个不等式同时成立：

推论：$u$ 与 $v$ 没有祖孙关系 $\Longleftrightarrow$ 两个区间 $[in_u,out_u]$ 与 $[in_v,out_v]$ 不交。因为 DFS 进一个子树、办完事、彻底退出，才会进入另一棵子树，两段区间不可能交叉。

下图把每个点的区间画成一条杆，包含与不交的关系一眼可见。

P4 祖先链上两个时间戳单调

若 $u$ 是 $v$ 的祖先，则

也就是越靠近根，$in$ 越小、$out$ 越大。因此按 $in$ 从小到大排序后，任何一个点都排在它所有后代的前面。

P5 后序与第二套序号：双 DFS 序

后序（退出序）就是“儿子先于父亲”的顺序，所以把点按后序排好后，从前往后处理，每次处理时儿子的信息已经齐了——树上 DP 和树上差分的汇总都靠这个顺序。

更有用的是退出序的逆序。它有一个等价的定义：把每个点的儿子列表顺序反转后再做一次 DFS，得到的进入序。把这个序记作 $rdfn$，则

$$ rdfn_u = n - \text{（$u$ 的退出计数）} + 1 $$

其中退出计数是 $u$ 在退出序中的名次。这时祖孙判定变成两维同向的不等式：

为什么非要第二维？只看 $in$ 挡不住“位置在 $v$ 左边、但不是 $v$ 的祖先”的点。样例树里把 $4$ 和 $5$ 都染黑，查询 $7$ 的祖先：$in_4 = 3 < in_7 = 5$，只看 $in$ 会把 $4$ 选成答案，但 $4$ 和 $7$ 分属 $2$ 的两个儿子，$4$ 根本不是祖先；补上 $rdfn_4 = 7 > rdfn_7 = 6$ 就把它排除了。

两维同向的好处是把“$v$ 的祖先”变成平面上左下角矩形 $[1,in_v] \times [1,rdfn_v]$ 里的点，于是可以交给线段树、树状数组做最值或计数查询。第一维编号的顺序、第二维编号的顺序恰好相反，所以一旦两个点不在一支上，两维的大小关系必然一正一反。

P6 欧拉序：区间最浅点就是 LCA

欧拉序长度是 $2n-1$，每个点出现多次。设 $pos(u)$ 是 $u$ 第一次出现的位置，则

其中 $E$ 是欧拉序。直观理由是：这段区间里出现的点全都落在 $\text{lca}(u,v)$ 的子树内，而 LCA 本身也在其中出现过，所以深度最小的那次出现只能是它。

算法证明

主命题：子树是连续区间（P1）

关键不变量：离开点 $u$ 时，计数器 $timer$ 的值恰好等于 $u$ 的子树内所有点的数量加上 $u$ 之前已经用掉的编号数。

对 $u$ 做归纳。记 $S_u$ 为 $u$ 的子树。

1. 进入 $u$ 时分配 $in_u$，此时 $S_u$ 中只有 $u$ 拿到了编号。
2. 设 $u$ 的儿子为 $v_1, v_2, \dots, v_k$。递归处理 $v_i$ 之前，$S_{v_1},\dots,S_{v_{i-1}}$ 已经全部编号完毕，而 $v_i$ 之后的子树一个点都没被访问；由归纳假设，处理完 $v_i$ 时，新占用的编号正好是 $S_{v_i}$ 中所有点。
3. 所有儿子处理完后，被分配过编号的点集恰好是 $\{u\} \cup S_{v_1} \cup \dots \cup S_{v_k} = S_u$，且它们拿到的编号是连续的一段，右端点就是当时的 $timer$，即 $out_u$。
4. 由第 2 步，在处理 $u$ 的任何后代期间，DFS 不可能跳到 $S_u$ 之外，所以这段编号里不会混进外部点。

于是 $S_u$ 与区间 $[in_u, out_u]$ 一一对应，P1 成立；顺带得到区间长度等于 $|S_u|$，即 P2。

P3：区间包含与祖先关系等价

• 若 $u$ 是 $v$ 的祖先，则 $v \in S_u$，由 P1 得 $in_u \leqslant in_v \leqslant out_u$。
• 若 $in_u \leqslant in_v \leqslant out_u$，则 $v$ 的编号落在 $u$ 的区间里，而这个区间里的点恰好是 $S_u$ 的点，所以 $v \in S_u$，即 $u$ 是 $v$ 的祖先。
• 若区间相交：存在下标 $i \in [in_u,out_u] \cap [in_v,out_v]$，则点 $order[i]$ 同时属于 $S_u$ 与 $S_v$，于是 $u$、$v$ 都是它的祖先。祖先构成一条链，所以 $u,v$ 中必有一个是另一个的祖先。
• 若其中一个是另一个的祖先：由 P1，后代那一段区间被祖先的区间完整包含，两区间必然相交。

两件事合起来就是：两个区间不交，当且仅当两点互不为祖先。

P4

设 $u$ 是 $v$ 的祖先且 $u \neq v$。由 P1，$in_v \in [in_u, out_u]$ 且 $v \neq u$，所以 $in_u < in_v$；又 $S_v \subseteq S_u$，两段区间都连续且 $S_v$ 的区间含于 $S_u$ 的区间，故 $out_v \leqslant out_u$。

P5：双 DFS 序为什么能判祖先

设第一遍 DFS 按父亲给定的儿子顺序走，第二遍把每个点的儿子顺序整个反转。

• 若 $u$ 是 $v$ 的祖先：两遍 DFS 都必须从 $u$ 走到 $v$，进入 $u$ 一定早于进入 $v$，所以 $in_u \leqslant in_v$ 且 $rdfn_u \leqslant rdfn_v$。
• 若 $u,v$ 互不为祖先：记 $l = \text{lca}(u,v)$，则 $u,v$ 分别落在 $l$ 的两个不同儿子的子树中。第一遍先走了其中一个分支，第二遍把 $l$ 的儿子顺序反转后，必然先走另一个分支。于是第一遍的大小关系在第二遍被颠倒：$in_u < in_v$ 时必有 $rdfn_u > rdfn_v$。两条不等式不可能同时成立。

P6：欧拉序区间的浅点

设 $w = \text{lca}(u,v)$，则 $u$ 与 $v$ 都在 $S_w$ 里。从 $u$ 的第一次出现走到 $v$ 的第一次出现期间，DFS 一直待在 $w$ 的子树里：一旦退出 $S_w$，就离开了 $w$，而 $v$ 还在 $S_w$ 中，再也回不去。

所以这段区间里记录的每个点都满足 $dep \geqslant dep_w$，而 $w$ 自己也在区间里出现过（$u \to v$ 的路线必须经过 $w$）。深度最小的那次出现于是正是 $w$。

复杂度分析

设树有 $n$ 个点。

• 预处理时间：每个点进入一次、每条边被父亲检查两次，$O(n)$。
• 预处理空间：邻接表 $O(n)$，in/out/sz/dep/order 各 $O(n)$，欧拉序 $O(n)$。
• 单次祖先判定：$O(1)$。
• 递归 DFS 的栈深度最坏为 $n$（链），迭代版同样需要 $O(n)$ 的显式栈。

代码模板

下面的模板不含 main，直接复制进题解即可。C++ 版用全局数组加自由函数，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

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

const int maxn = 1e5 + 5;

// 不用 struct 的 DFS 序：全局数组 + 自由函数。
// 用法：
//   1. 读边：tree[u].push_back(v); tree[v].push_back(u);
//   2. reset_order();  dfs_order(root, 0);
//   3. 之后直接用 in_ / out_ / sz / dep / order_，并用 is_ancestor / subtree_size 查询。
//
// 编号从 1 开始，根的 in_ 一定是 1；父亲的哨兵点取 0，dep[0] = 0。
// 预处理是递归 DFS，链形树深度可达 n；n 很大时开大栈（ulimit -s unlimited）或改用迭代版。

vector<int> tree[maxn];

int in_[maxn], out_[maxn];  // 子树 u 对应时间戳区间 [in_[u], out_[u]]
int sz[maxn], dep[maxn];    // 子树大小、深度（根的深度为 1）
int order_[maxn];           // order_[i] = 第 i 个被访问的点
int timer;                  // 时间戳计数器，取值 1..n

void reset_order() { timer = 0; }  // 多组数据必须清空，否则编号会接着上一组涨

void dfs_order(int u, int fa) {
    in_[u] = ++timer;  // 进入 u：拿一个时间戳
    order_[timer] = u;
    sz[u] = 1;
    for (int v : tree[u]) {
        if (v == fa) continue;  // 无向边存成双向，跳过父亲就是只往下走
        dep[v] = dep[u] + 1;
        dfs_order(v, u);
        sz[u] += sz[v];
    }
    out_[u] = timer;  // 退出 u：子树全部访问完，timer 就是区间右端点
    // 等价写法：out_[u] = in_[u] + sz[u] - 1;
}

// u 是不是 v 的祖先（u == v 也算）。等价写法：in_[u] <= in_[v] && out_[v] <= out_[u]
bool is_ancestor(int u, int v) { return in_[u] <= in_[v] && in_[v] <= out_[u]; }

int subtree_size(int u) { return out_[u] - in_[u] + 1; }  // 恒等于 sz[u]

// 欧拉序：进入写一次，每从一个儿子返回再写一次，长度 2n-1。
// 用它配合 RMQ（区间深度最小值）可以求 LCA。
int euler[2 * maxn], etot;

void dfs_euler(int u, int fa) {
    euler[++etot] = u;
    for (int v : tree[u]) {
        if (v == fa) continue;
        dfs_euler(v, u);
        euler[++etot] = u;  // 从儿子 v 退回 u 时，再写一次 u
    }
}
    

        
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

        # 依赖模块级全局邻接表 tree：使用前先 tree = [[] for _ in range(n + 1)]，
# 再加无权边 tree[u].append(v) 和 tree[v].append(u)。点编号 1..n，根的 in_ 是 1。
# in_ / out 是进入、退出时间戳，子树 u 恰好占区间 [in_[u], out[u]]，长度就是子树大小。
# 深树（链）递归会爆栈，所以这里用显式栈迭代；in 是 Python 关键字，故写作 in_。

type Graph = list[list[int]]

tree: Graph = []


class DFSOrder:
    """DFS 序（先序时间戳）与欧拉序。"""

    n: int
    in_: list[int]
    out: list[int]
    sz: list[int]
    dep: list[int]
    order: list[int]  # order[i] = 第 i 个被访问的点
    euler: list[int]  # 欧拉序，长度 2n-1（不是先序！每个点会重复出现）
    timer: int
    etot: int

    def __init__(self, n: int) -> None:
        self.n = n
        self.in_ = [0] * (n + 1)
        self.out = [0] * (n + 1)
        self.sz = [0] * (n + 1)
        self.dep = [0] * (n + 1)
        self.order = [0] * (n + 1)
        self.euler = [0] * (2 * n)
        self.timer = 0
        self.etot = 0

    def build(self, root: int = 1) -> None:
        """迭代 DFS 求先序时间戳；多组数据必须重建对象（或把 timer 清 0）。"""
        self.timer = 0
        # 栈元素 (点, 父亲, 下一条待处理的邻边下标)，下标 0 兼作“还没进入”的标记。
        stack: list[tuple[int, int, int]] = [(root, 0, 0)]
        while stack:
            u, fa, idx = stack.pop()
            if idx == 0:  # 第一次弹到 u：等价于递归版的“进入”
                self.timer += 1
                self.in_[u] = self.timer
                self.order[self.timer] = u
                self.sz[u] = 1

            advanced = False
            while idx < len(tree[u]):
                v = tree[u][idx]
                idx += 1
                if v == fa:
                    continue
                self.dep[v] = self.dep[u] + 1
                stack.append((u, fa, idx))  # 记住自己处理到哪条边，回来继续
                stack.append((v, u, 0))
                advanced = True
                break

            if not advanced:  # 邻边走完：等价于递归版的“退出”
                self.out[u] = self.timer
                if stack:
                    self.sz[stack[-1][0]] += self.sz[u]  # 子树大小交回父亲

    def is_ancestor(self, u: int, v: int) -> bool:
        """O(1) 判断 u 是不是 v 的祖先（u == v 也算）。"""
        return self.in_[u] <= self.in_[v] <= self.out[u]

    def subtree_size(self, u: int) -> int:
        return self.out[u] - self.in_[u] + 1  # 恒等于 self.sz[u]

    def build_euler(self, root: int = 1) -> None:
        """欧拉序：进入写一次，每从一个儿子返回再写一次，长度 2n-1。"""

        def dfs(u: int, fa: int) -> None:
            self.etot += 1
            self.euler[self.etot] = u
            for v in tree[u]:
                if v == fa:
                    continue
                dfs(v, u)
                self.etot += 1
                self.euler[self.etot] = u

        self.etot = 0
        dfs(root, 0)
    

代码实现

完整程序读入一棵树和若干祖孙询问，输出两套编号、子树大小与深度，以及每次询问的结果。

        
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

        // 完整实现：读一棵 n 个点的树，输出两套编号、子树大小和深度，再回答祖孙询问。
// 输入：
//   n
//   n-1 行 u v（无向边）
//   q
//   q 行 u v（问 u 是不是 v 的祖先）
// 输出：先序、欧拉序、每个点的 in/out/size/dep，以及每次询问的 yes/no。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

vector<int> tree[maxn];
int in_[maxn], out_[maxn], sz[maxn], dep[maxn], order_[maxn];
int euler[2 * maxn];
int timer, etot;

void dfs_order(int u, int fa) {
    in_[u] = ++timer;
    order_[timer] = u;
    sz[u] = 1;
    for (int v : tree[u]) {
        if (v == fa) continue;
        dep[v] = dep[u] + 1;
        dfs_order(v, u);
        sz[u] += sz[v];
    }
    out_[u] = timer;  // 子树访问完了，timer 就是区间右端点
}

void dfs_euler(int u, int fa) {
    euler[++etot] = u;
    for (int v : tree[u]) {
        if (v == fa) continue;
        dfs_euler(v, u);
        euler[++etot] = u;
    }
}

bool is_ancestor(int u, int v) { return in_[u] <= in_[v] && in_[v] <= out_[u]; }

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

    int n;
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dep[1] = 1;
    dfs_order(1, 0);
    dfs_euler(1, 0);

    cout << "order:";
    for (int i = 1; i <= n; i++) cout << ' ' << order_[i];
    cout << '\n';

    cout << "euler:";
    for (int i = 1; i <= etot; i++) cout << ' ' << euler[i];
    cout << '\n';

    for (int u = 1; u <= n; u++) {
        cout << u << ": in=" << in_[u] << " out=" << out_[u]
             << " size=" << sz[u] << " dep=" << dep[u] << '\n';
    }

    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << u << ' ' << v << ' ' << (is_ancestor(u, v) ? "yes" : "no") << '\n';
    }
    return 0;
}
    

        
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

        # 完整实现（Python 版）：与 C++ 版输出完全一致。
# 输入：n；n-1 行边；q；q 行祖孙询问（问 u 是不是 v 的祖先）。
# 输出：先序、欧拉序、每个点的 in/out/size/dep，以及每次询问的 yes/no。
# 深树（链）递归会爆栈，遍历统一用显式栈迭代。
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    pos = 0
    n = int(data[pos])
    pos += 1

    tree: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(data[pos])
        v = int(data[pos + 1])
        pos += 2
        tree[u].append(v)
        tree[v].append(u)

    in_ = [0] * (n + 1)
    out = [0] * (n + 1)
    sz = [0] * (n + 1)
    dep = [0] * (n + 1)
    order = [0] * (n + 1)

    # ---------- 先序：进入记 in，退出记 out ----------
    dep[1] = 1
    timer = 0
    # 栈元素 (点, 父亲, 下一条待处理的邻边下标)，下标 0 兼作“还没进入”的标记
    stack: list[tuple[int, int, int]] = [(1, 0, 0)]
    while stack:
        u, fa, idx = stack.pop()
        if idx == 0:  # 第一次弹到 u
            timer += 1
            in_[u] = timer
            order[timer] = u
            sz[u] = 1
        advanced = False
        while idx < len(tree[u]):
            v = tree[u][idx]
            idx += 1
            if v == fa:
                continue
            dep[v] = dep[u] + 1
            stack.append((u, fa, idx))
            stack.append((v, u, 0))
            advanced = True
            break
        if not advanced:  # 邻边走完
            out[u] = timer
            if stack:
                sz[stack[-1][0]] += sz[u]

    # ---------- 欧拉序：进入写一次，每从一个儿子返回再写一次 ----------
    euler: list[int] = []

    def dfs_euler(u: int, fa: int) -> None:
        euler.append(u)
        for v in tree[u]:
            if v == fa:
                continue
            dfs_euler(v, u)
            euler.append(u)

    sys.setrecursionlimit(max(1000, n * 2 + 10))  # 欧拉序这里用递归，深度仍是 n
    dfs_euler(1, 0)

    print("order:", *order[1:])
    print("euler:", *euler)
    for u in range(1, n + 1):
        print(f"{u}: in={in_[u]} out={out[u]} size={sz[u]} dep={dep[u]}")

    q = int(data[pos])
    pos += 1
    ans: list[str] = []
    for _ in range(q):
        u = int(data[pos])
        v = int(data[pos + 1])
        pos += 2
        ok = in_[u] <= in_[v] <= out[u]
        ans.append(f"{u} {v} {'yes' if ok else 'no'}")
    if ans:
        sys.stdout.write("\n".join(ans) + "\n")


if __name__ == "__main__":
    main()
    

测试用例

输入：

7
1 2
1 3
2 4
2 5
5 7
3 6
4
2 7
4 5
3 6
4 7

输出：

order: 1 2 4 5 7 3 6
euler: 1 2 4 2 5 7 5 2 1 3 6 3 1
1: in=1 out=7 size=7 dep=1
2: in=2 out=5 size=4 dep=2
3: in=6 out=7 size=2 dep=2
4: in=3 out=3 size=1 dep=3
5: in=4 out=5 size=2 dep=3
6: in=7 out=7 size=1 dep=3
7: in=5 out=5 size=1 dep=4
2 7 yes
4 5 no
3 6 yes
4 7 no

看几处关键数字：

• 点 $2$ 的子树是 $\{2,4,5,7\}$，区间 $[2,5]$ 长度正好是 $4$；
• 叶子 $4,6,7$ 的 $in$ 与 $out$ 相等，区间退化成一点；
• 询问 4 5：$in_4=3, in_5=4$，虽然 $4$ 的编号更小，但 $out_4=3 < in_5$，区间不交，所以 $4$ 不是 $5$ 的祖先。

应用分类详解

DFS 序的本质是两个方向的翻译：把“子树”翻译成“区间”，把“祖先”翻译成“区间包含”。

一、子树上的查询与修改

典型模式： 单点修改 + 子树查询，或子树修改 + 单点/子树查询。 识别信号： 题面出现“以 $u$ 为根的子树”“子树内所有点”“给整棵子树加 $x$”。 核心建模： 把点权按 in[u] 放到数组上，子树操作就是区间操作，交给树状数组或线段树。

二、祖先关系与“点在不在子树里”

典型模式： 反复判断 $u$ 是否为 $v$ 的祖先，或统计每个点子树内满足条件的点数。 识别信号： “祖先”“后代”“是否属于某棵子树”“以 $u$ 为根的子树中有几个”。 核心建模： 用 in_u ≤ in_v ≤ out_u 做 $O(1)$ 判定；统计类问题把点集按 in 排序后二分，子树就变成一个下标区间。

三、路径与子树的互化

典型模式： 给一条路径整体加值，最后统计每个点；或给一个点加值，查询根到某点的路径和。 识别信号： “路径加”“路径上的点被经过几次”“最后输出每个点的值”。 核心建模： 利用“$x$ 在根到 $u$ 的路径上 $\Longleftrightarrow$ $u \in \text{subtree}(x)$”，把路径与子树互换，再用区间操作或差分。

四、按 DFS 序排序的离线结构

典型模式： 每次询问只涉及少量关键点，或需要把树上点集变成连续段。 识别信号： “每次给出 $k$ 个关键点”“按顺序插入点并回答连通块”“统计子树内某些颜色的数量”。 核心建模： 把所有点按 in 排序，子树变成区间；关键点集按 in 排序后，相邻两点（含首尾）的 LCA 足以还原虚树的所有分叉点。

五、LCA 与欧拉序

典型模式： 大量询问两点 LCA，且树是静态的。 识别信号： “最近公共祖先”“两点距离”“路径是否相交”。 核心建模： 欧拉序 + RMQ 把 LCA 变成区间最小值，预处理 $O(n \log n)$、查询 $O(1)$；需要改树结构时改用其他方法。

六、定制一套自己的“dfs 序”

典型模式： 子树操作还不够，还要支持任意路径的查询与修改。 识别信号： “路径加/路径求和”“查询路径上第一个黑点”。 核心建模： 改变编号的规则。让重儿子先编号，得到重链剖分的序（同一条重链连续）；或者用两遍儿子顺序相反的 DFS 得到双序，把祖孙关系变成二维偏序。

易错点

• out 写成 in[u] + 1：只有叶子才成立。正确做法是退出时取当前的 timer，或者用 in[u] + sz[u] - 1。
• 祖先判定写反方向：写成 in[u] <= in[v] && out[u] <= out[v] 是错的，需要的是 out[v] <= out[u]（祖先的右端点更大）。
• 多组数据忘记清空 timer：timer 必须每组归零，否则编号会接着上一组继续涨。
• 父亲的哨兵不一致：常见做法是让根的父亲为 $0$，并保证 dep[0] = 0；如果改成“根的父亲是自己”，要检查 v == fa 的跳过逻辑是否会把根卡死。
• 把欧拉序当先序：欧拉序长度是 $2n-1$，拿它去开 $n$ 大小的数组会越界。
• 递归 DFS 爆栈：链形树上深度是 $n$，$n \geqslant 10^5$ 时就要考虑迭代写法或开大栈。

经典例题

• luogu-P3258 松鼠的新家：按访问顺序把每段路径整体加一，等价于树上差分；最后按逆 $in$ 序把儿子的贡献推给父亲，一次遍历得到每个点被经过的次数。
• luogu-P3128 Max Flow P：点差分的模板题，路径两端加一、LCA 与 LCA 的父亲减一，答案在按逆 $in$ 序求子树和时得到。
• luogu-P2495 消耗战：每次询问给出一批关键点，按 in 排序后加入相邻 LCA 就能建出虚树，把 $O(n)$ 的 DP 压到 $O(k)$。
• luogu-P1600 天天爱跑步：把每个观察员能被谁看到写成关于 $dep$ 与 in 的方程，按逆 $in$ 序合并桶统计贡献。
• luogu-P4116 Qtree3：查询根到某点路径上最浅的黑点。单用 $in$ 无法排除“在左边但不在这条路径上”的黑点，改用双 DFS 序把它变成平面上的左下角矩形，配合线段树二分 $O(\log n)$。
• luogu-P3384 【模板】树链剖分：把“先重儿子”写进编号规则，子树仍然连续，同时重链也连续，于是路径操作也能落在区间上。

参考

本书相关章节：

• 图的遍历：DFS 本身的过程与实现方式。
• 树的存储：邻接表、父亲与孩子，以及定根的做法。
• 倍增求 LCA：用 in/out 做 $O(1)$ 祖先判定，以及路径拆成两段。
• 树链剖分：把重儿子优先写进 DFS 序，一条重链编号连续。
• 树状数组：子树区间查询与单点修改的常用搭配。
• 树上差分：把路径修改转成子树上的加减，最后按逆 $in$ 序汇总。