Day 9 讲义：树上 DFS、DFS 序与子树区间

树是一张没有环的连通图。树题最先做的事是：任选一个根，把无根树变成有父子关系的树。

1. DFS 进入与退出时做什么

递归 DFS 常分三段：

void dfs(int u, int fa){
    // 进入 u：初始化 u 的信息
    for(int v: g[u]){
        if(v == fa) continue;
        dfs(v, u);
        // 子树 v 已完成：把 v 的信息合并到 u
    }
    // 离开 u：u 的子树信息完整
}

进入时适合维护路径状态；子节点返回后适合合并子树信息。

2. 子树大小与叶子数

最基本的子树大小：

sz[u] = 1;
for(int v: g[u]) if(v != fa){
    dfs(v, u);
    sz[u] += sz[v];
}

982C 中，一条边可以切开当且仅当子树大小为偶数。原因：切开后两边节点数都必须为偶数。

1056D 中，叶子数递归：

无儿子：leaf[u]=1；
有儿子：leaf[u]=所有儿子 leaf 之和。

树形递归的核心是：父节点答案由儿子答案合并而来。

3. 路径状态：580C

从根走到当前点时，连续猫的数量只依赖：

父亲路径末尾连续猫数；
当前点是否有猫。

设 cnt 是到当前点为止的连续猫数：

if(cat[u]) cnt++;
else cnt = 0;

若 cnt > m，这条路径以后无论怎么走都不合法，直接停止递归。

这叫剪枝：状态已经违反约束，不必继续访问后代。

4. DFS 序：把子树压成连续区间

进入节点 u 时记录：

tin[u] = ++timer
ord[timer] = u

若按先序 DFS 访问，u 的整棵子树在 ord 中必然连续：

[tin[u], tin[u] + sz[u] - 1]

这就是 1006E 的关键。询问“u 子树 DFS 序中第 k 个节点”：

int pos = tin[u] + k - 1;
if(pos >= tin[u] + sz[u]) cout << -1;
else cout << ord[pos];

4.1 模板

const int N = 200000 + 10;
vector<int> g[N];
int tin[N], sz[N], ord[N], timer;

void dfs(int u, int fa){
    tin[u] = ++timer;
    ord[timer] = u;
    sz[u] = 1;
    for(int v: g[u]){
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

5. 930A：按深度统计

DFS 时额外传入 dep：

cnt[dep]++;

最后统计 cnt[dep] 为奇数的层数即可。

树的“层”不是 BFS 专属概念；DFS 也能维护深度。

6. 763A：冲突边只给两个候选根

若一条边两端颜色不同，那么合法根必须在这条边的某一端。否则从根到这两个点的路径会经过该边，但两端不可能同时满足“同色子树”的要求。

所以：

1. 找任意一条颜色不同的边 (x,y)；
2. 分别尝试 x、y 作为根；
3. DFS 检查每条边的子树是否颜色一致。

把 n 个候选根缩成 2 个，是树题常见降维方式。

7. 易错点

• 无向树 DFS 必须跳过父亲，否则会在父子间来回递归；
• 叶子定义要看“除父亲外是否有儿子”；
• DFS 序从 1 还是 0 开始要统一；
• 递归深度可能到 2e5，链状树需要注意栈深；
• 子树区间右端点是 tin[u]+sz[u]-1。

8. 今日总结

进点记路径，出点合子树。
子树大小能切边，叶子数量向上加。
DFS 序把树压数组，子树就是连续段。
冲突边先定候选根，树题常靠性质降范围。