DFS序

问题模型

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

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

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

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

再把点按进入时间排成一排，记 $order[i]$ 为第 $i$ 个被访问的点。$in, out$ 两个数组加一条 $order$，就是本文所有性质的全部原料。

核心直觉

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

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

也就是说：树上的“子树”这种递归结构，在时间轴上是连续的一段。

上图里每个点的第二个数字就是它的区间 $[in_u, out_u]$。可以看到区间是嵌套或互不相交的：$[2,5]$ 把 $[3,3]$、$[4,5]$、$[5,5]$ 整段包住，而 $[6,7]$ 和 $[2,5]$ 完全不重叠。这种嵌套结构正是下面所有性质的基础。

把点按 $in$ 排成一排，子树的连续性就更直观了：

蓝色的四格是子树 $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$。

代码模板

下面的模板不含 main，直接复制进题解。递归版够短，链形树怕爆栈时换用同文件里的 dfs_order_iter。

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

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

const int maxn = 1e5 + 5;

// DFS 序：全局数组 + 自由函数，不含 main，直接复制进题解。
// 用法：
//   1. 读边：tree[u].push_back(v); tree[v].push_back(u);
//   2. dfs_order(1, 0);          // 递归版
//      或 dfs_order_iter(1);     // 链形树怕爆栈时用迭代版
//   3. 之后直接用 in_ / out_ / sz / dep / order_，
//      再用 is_ancestor(u, v) 判祖孙、subtree_size(u) 取子树大小。
//
// 编号 1..n，根的 in_ 一定是 1；父亲哨兵取 0，dep[0] = 0。
// 递归深度最坏是 n（链），n >= 1e5 时开大栈（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 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;
}

// 迭代版：栈里放 (点, 父亲, 下一条待处理的邻边下标)
void dfs_order_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;
            dep[v] = dep[u] + 1;
            st.back() = make_tuple(u, fa, idx);  // 记住自己处理到哪条边
            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];  // 子树大小交回父亲
            }
        }
    }
}

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

迭代版要记住两件事：栈元素里的 idx 兼作“是否已经进入过”的标记；sz 要在弹出时结算给父亲，因为那时子树已经全部处理完。

完整代码

读入一棵树和若干祖孙询问，输出先序、欧拉序、每个点的四元组，以及每次询问的结果。

两个版本输出完全一致（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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

// 完整实现：读一棵 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;
}

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;
        bool ok = is_ancestor(u, v);
        cout << u << ' ' << v << ' ' << (ok ? "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()

性质

下面都以“$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$ 的祖先且 $u \neq v$，则

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

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

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

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

其中 $\mathrm{cnt}(u)$ 是 $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 本身也在其中出现过，所以深度最小的那次出现只能是它。详见 [ Rbook: 爬树法求lca]。

正确性证明

P1：子树是连续区间

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

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

1. 进入 $u$ 时分配 $in_u$，此时 $S_u$ 中只有 $u$ 拿到了编号。
2. 设 $u$ 的儿子为 $v_1, \dots, v_k$。处理 $v_i$ 之前，$S_{v_1},\dots,S_{v_{i-1}}$ 已经全部编号完毕，$v_{i+1}$ 之后的子树一个点都没被访问；由归纳假设，处理完 $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，后代那段区间被祖先的区间完整包含，两区间必然相交。

合起来就是：两个区间不交 $\Longleftrightarrow$ 两点互不为祖先。

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$，两段连续区间一段含于另一段，故 $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 \in S_w$。从 $u$ 的第一次出现走到 $v$ 的第一次出现期间，DFS 一直待在 $w$ 的子树里：一旦退出 $S_w$ 就离开了 $w$，而 $v$ 还在 $S_w$ 中，再也回不去。

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

复杂度分析

设树有 $n$ 个点。

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

测试用例

输入：

1
2
3
4
5
6
7
8
9
10
11
12

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

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13

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 \leqslant in_v \leqslant 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 \leqslant in_v \wedge out_u \leqslant out_v$ 是后代条件；判祖先要的是 $out_v \leqslant out_u$。
• 多组数据忘记清 timer：不清就会接着上一组的编号继续涨，所有区间全错。
• 父亲哨兵不一致：常见做法是根的父亲取 $0$ 并令 $dep_0 = 0$；如果改成“根的父亲是自己”，要检查跳过 v == fa 的逻辑会不会把根卡死。
• 把欧拉序当先序：欧拉序长度是 $2n-1$，拿它开 $n$ 大小的数组会越界。
• 递归爆栈：链形树深度是 $n$，$n \geqslant 10^5$ 时考虑迭代写法或开大栈。

练习题目

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

参考

• 书的存储与遍历：[ Rbook: 树的入门]、[ Rbook: 图的遍历]；
• 差分思想：[ Rbook: 差分]，树上版本见 [ Rbook: 树上差分]；
• 倍增与 LCA：[ Rbook: binary jump]、[ Rbook: 爬树法求lca]；
• 子树区间常用的数据结构：[ Rbook: 区间更新]。