树的问题

前言

树是图论中最”规矩”的结构——$N$ 个节点恰好 $N-1$ 条边，连通且无环。这听起来像是限制，实际上是巨大的简化。

在一般图上，“两个节点之间可能有多条路径”，导致问题复杂。但在树上，两个节点之间有且仅有一条路径——没有”选哪条路”的烦恼。树的无环性让 DP、距离计算、路径查询都变得简单。

树在竞赛中极其常见。很多看起来是”图”的问题，实际上可以简化成树（比如 MST 本身就是一棵树，SCC 缩点后变成 DAG 也就是”广义的树”）。掌握树上的基本操作是解决复杂图论问题的前提。

教材（Tessoku Book 9.5 B65 Road to Promotion Hard 和 9.6 B66 Typhoon）展示了树上 DFS 和并查集在树问题中的应用。

问题的本质

树为什么特殊？

树有几个独特的性质，每一个都让算法变得更简单：

1. 任意两点之间有且仅有一条路径。一般图中可能有多条路径（甚至无限多条，如果有环），但树没有环——路径唯一。这意味着”最短路”在树上退化为”唯一的路”。
2. $N$ 个节点恰好 $N-1$ 条边。少一条就不连通，多一条就有环。这个精确的约束让很多计数问题变简单。
3. 删除任何一条边都会把树分成两棵不连通的子树。这个”割”性质在 Kruskal 的证明中已经见过。
4. 添加任何一条边都会形成环。因为没有环，加一条边就创造了第二条路径——形成环。

子树 = DFS 序上的连续区间

这是一棵树上最强大的性质之一。选一个根节点，做一次 DFS，记录每个节点的进入时间 tin[u] 和离开时间 tout[u]。

关键观察：节点 $u$ 的子树中的所有节点，DFS 序恰好是 $[tin[u], tout[u]]$ 这个连续区间。

为什么？DFS 进入 $u$ 后，会完整地遍历 $u$ 的整棵子树，然后才离开 $u$。所以子树中所有节点的进入时间都夹在 tin[u] 和 tout[u] 之间，而且区间内没有非子树的节点（DFS 不会跳到其他子树）。

这个性质意味着：树上”子树查询”可以转化为”区间查询”。比如”子树中所有节点的权值和”变成”DFS 序上一个区间的和”——直接用前缀和或 BIT 解决，$O(\log N)$。

LCA：路径一定经过最近公共祖先

最近公共祖先（Lowest Common Ancestor, LCA）：节点 $u$ 和 $v$ 的 LCA 是同时是 $u$ 和 $v$ 的祖先中，深度最大的那个。

为什么 LCA 如此重要？因为在树上，$u$ 到 $v$ 的路径恰好是 $u \to \text{LCA}(u,v) \to v$。路径长度 $= \text{depth}(u) + \text{depth}(v) - 2 \times \text{depth}(\text{LCA})$。

为什么路径一定经过 LCA？因为从 $u$ 到 $v$ 必须”先向上走、再向下走”，转折点就是 LCA——最深的公共祖先。任何比 LCA 更浅的公共祖先都在 LCA 的上方，不是转折点。

教材的应用：树上 DFS 和逆序并查集

教材 9.5 B65 Road to Promotion Hard 展示了树上 DFS 的典型应用：计算每个节点的”阶級”（子树中最大深度）。关键观察：“进入子树时设初值，离开子树时用子节点的结果更新”——这就是树上 DP 的通用模式。

教材 9.6 B66 Typhoon 展示了一个巧妙的”逆序”技巧：删除边的操作不能直接用并查集处理（并查集只支持合并，不支持删除）。但如果倒过来处理所有操作，“删除”就变成了”添加”——并查集就能用了。

理论 + 代码

DFS 序与子树区间

#include <vector>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN], timer = 0;

void dfs(int u, int parent) {
    tin[u] = ++timer;                     // ① 进入时间
    for (int v : adj[u]) {
        if (v != parent) dfs(v, u);       // ② 不走回头路
    }
    tout[u] = timer;                      // ③ 离开时间
}

逐行解析：

• ① 进入节点 $u$ 时记录时间。timer 是全局递增的。
• ② 树是无向图，需要 parent 参数防止走回头路。这和一般图的 visited 不同——树中每条边只有一个非父方向，不需要数组标记。
• ③ 离开时记录时间。$u$ 的子树中所有节点的 tin 都在 $[tin[u], tout[u]]$ 之间。

LCA（倍增法）

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100006, LOG = 20;
vector<int> adj[MAXN];
int depth[MAXN], up[MAXN][LOG];

void dfs(int u, int parent) {
    up[u][0] = parent;                    // ① 2^0 = 1 步上的祖先 = 父节点
    for (int k = 1; k < LOG; k++)
        up[u][k] = up[up[u][k-1]][k-1];  // ② 倍增：2^k = 2^(k-1) + 2^(k-1)
    for (int v : adj[u]) {
        if (v != parent) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v); // ③ 保证 u 更深
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; k++)
        if ((diff >> k) & 1) u = up[u][k]; // ④ 把 u 提到和 v 同一深度
    if (u == v) return u;                   // ⑤ v 是 u 的祖先
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {         // ⑥ 从远处往近处跳
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0];                        // ⑦ LCA = 两者父节点
}

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)]; // ⑧ 路径长度
}

逐行解析：

• ② 倍增预处理的精髓：up[u][k] = $u$ 往上走 $2^k$ 步到达的祖先。$2^k = 2^{k-1} + 2^{k-1}$，所以走两遍 $2^{k-1}$ 步就等于走 $2^k$ 步。预处理 $O(N \log N)$。
• ④ 把 $u$ 提到和 $v$ 同一深度：差值 diff 的二进制表示决定了跳哪些 $2^k$ 步。
• ⑥ 从大步到小步尝试：如果跳 $2^k$ 步后 $u$ 和 $v$ 的祖先不同，就跳。这样两者会停在 LCA 的正下方。
• ⑧ 路径长度公式：$u$ 到根的距离 + $v$ 到根的距离 - 2 × LCA 到根的距离。为什么减 2 倍？因为 LCA 到根的这段被两边都算了一次。

树的直径

树的直径是树上最长的路径。求法：从任意节点出发 BFS 找最远的节点 $a$，再从 $a$ 出发 BFS 找最远的节点 $b$，$a$ 到 $b$ 的路径就是直径。

为什么两次 BFS 就够？ 因为从任意节点出发的最远节点一定是直径的端点之一。这是树的特殊性质（一般图不成立）。

例题

例题 1：T90 003 — Longest Circular Road（★4）

题目：$N$ 个城镇，$N-1$ 条双向道路（一棵树）。从某个城镇出发，经过若干城镇回到起点，最多经过多少个不同的城镇？

数据范围：$2 \le N \le 10^5$

—— AtCoder Typical 90 003

分析：在树上走一圈回到起点 = 走树的直径（最远路径），走过的城镇数 = 直径长度 + 1。

代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN];
int dist[MAXN];

int farthest(int start) {
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[start] = 0; q.push(start);
    int far = start;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                if (dist[v] > dist[far]) far = v;
                q.push(v);
            }
        }
    }
    return far;
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int a = farthest(1);         // ① 第一次 BFS：从 1 找最远点
    int b = farthest(a);         // ② 第二次 BFS：从 a 找最远点
    printf("%d\n", dist[b] + 1); // ③ 城镇数 = 距离 + 1
    return 0;
}

逐行解析：

• ①② 两次 BFS 找直径端点。
• ③ 直径长度 = dist[b]（从 $a$ 到 $b$ 的距离），城镇数 = 距离 + 1。

---

例题 2：T90 039 — Tree Distance（★5）

题目：$N$ 个节点的树。对每个节点 $k$，求 $k$ 到其他所有节点的距离之和。

数据范围：$2 \le N \le 10^5$

—— AtCoder Typical 90 039

分析：经典换根 DP。先以 1 为根算 $ans[1]$，然后一次 DFS 把答案传递给子节点。

关键公式：当根从 $u$ 变为 $v$（$v$ 是 $u$ 的子节点）时：

• $v$ 的子树里所有节点距离减 1（共 $subsize[v]$ 个）
• 其余节点距离加 1（共 $N - subsize[v]$ 个）
• 所以 $ans[v] = ans[u] + N - 2 \times subsize[v]$

代码：

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN];
long long ans[MAXN];
int subsize[MAXN];
int N;

void dfs1(int u, int parent, int depth) {
    subsize[u] = 1;
    ans[1] += depth;              // ① 以 1 为根的距离和
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs1(v, u, depth + 1);
        subsize[u] += subsize[v]; // ② 子树大小
    }
}

void dfs2(int u, int parent) {
    for (int v : adj[u]) {
        if (v == parent) continue;
        ans[v] = ans[u] + N - 2 * subsize[v]; // ③ 换根公式
        dfs2(v, u);
    }
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs1(1, -1, 0); // 第一次 DFS：以 1 为根算初始答案
    dfs2(1, -1);    // 第二次 DFS：传递答案
    for (int i = 1; i <= N; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

逐行解析：

• ① ans[1] = 所有节点到 1 的距离之和。DFS 时累加 depth。
• ② subsize[u] = $u$ 的子树大小，换根公式需要。
• ③ 核心公式：根从 $u$ 变为 $v$，$v$ 的子树里距离 -1，其余 +1。净变化 = $-(subsize[v]) + (N - subsize[v]) = N - 2 \times subsize[v]$。

验证：$N=3$，边 1-2, 2-3。dfs1 算出 ans[1] = 0+1+2 = 3。换根：ans[2] = 3+3-2×2 = 2, ans[3] = 2+3-2×1 = 3。距离和：节点1=[1+2=3], 节点2=[1+1=2], 节点3=[2+1=3]。✓

---

例题 3：TB B66 — Typhoon（逆序并查集）

题目：$N$ 个车站 $M$ 条铁路。$Q$ 个查询：① 第 $x$ 条路线停运。② 判断车站 $u$ 和 $v$ 是否连通。停运只增不减。

—— AtCoder Tessoku Book B66

分析：操作只有”删边”和”查询连通性”。直接删边不好做（并查集只支持加边不支持删边）。但逆序处理就变成”加边 + 查询”！

1. 记录所有被删的边。初始只保留从未被删的边，建并查集
2. 倒序处理查询：遇到”查询”用并查集判断，遇到”删边”变成”加回这条边”

代码：

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100006;
int parent[MAXN], rnk[MAXN];
int find(int x) { return parent[x]==x ? x : parent[x]=find(parent[x]); }
void unite(int x, int y) {
    int rx=find(x), ry=find(y);
    if(rx==ry) return;
    if(rnk[rx]<rnk[ry]) parent[rx]=ry;
    else if(rnk[rx]>rnk[ry]) parent[ry]=rx;
    else { parent[ry]=rx; rnk[rx]++; }
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    pair<int,int> edges[M+1];
    for (int i = 1; i <= M; i++) scanf("%d%d", &edges[i].first, &edges[i].second);
    bool deleted[M+1] = {};
    int Q;
    scanf("%d", &Q);
    vector<tuple<int,int,int>> queries(Q); // (type, x, u/v)
    for (int i = 0; i < Q; i++) {
        int t; scanf("%d", &t);
        if (t == 1) {
            int x; scanf("%d", &x);
            queries[i] = {1, x, 0};
            deleted[x] = true; // ① 标记被删的边
        } else {
            int u, v; scanf("%d%d", &u, &v);
            queries[i] = {2, u, v};
        }
    }
    // ② 初始：只保留未被删除的边
    for (int i = 1; i <= N; i++) { parent[i] = i; rnk[i] = 0; }
    for (int i = 1; i <= M; i++)
        if (!deleted[i]) unite(edges[i].first, edges[i].second);
    // ③ 逆序处理查询
    vector<string> results;
    for (int i = Q - 1; i >= 0; i--) {
        auto [type, a, b] = queries[i];
        if (type == 1) {
            unite(edges[a].first, edges[a].second); // "删边"变成"加边"
        } else {
            results.push_back(find(a) == find(b) ? "Yes" : "No");
        }
    }
    // ④ 反转输出（因为逆序处理了）
    for (int i = results.size() - 1; i >= 0; i--)
        printf("%s\n", results[i].c_str());
    return 0;
}

逐行解析：

• ① 先记录所有要被删除的边。
• ② 初始只加入永远不会被删的边，建好并查集。
• ③ 逆序遍历查询。“删边”操作变成了”加边”操作，直接 unite。“查询”操作用 find 判断。
• ④ 因为逆序处理，答案也要逆序输出。

---

例题 4：树上路径查询（LCA 应用）

场景：$N$ 个节点的树，每条边有权值。$Q$ 个查询：节点 $u$ 到 $v$ 的路径上边权之和。

数据范围：$1 \le N, Q \le 10^5$

分析：用 LCA + 深度前缀和。path_sum[u] = 从根到 $u$ 的路径权值和。则 $u$ 到 $v$ 的路径权值和 = $path\_sum[u] + path\_sum[v] - 2 \times path\_sum[lca(u,v)]$。

代码：

long long path_sum[MAXN]; // 根到每个节点的路径权值和

void dfs_weight(int u, int parent) {
    for (auto [v, w] : adj[u]) {
        if (v == parent) continue;
        path_sum[v] = path_sum[u] + w; // ① 前缀和
        dfs_weight(v, u);
    }
}

// 查询：path_sum[u] + path_sum[v] - 2 * path_sum[lca(u, v)]

参考文献

理论讲义 — AtCoder Algorithm Lectures

• グラフ理論用語集（木、LCA、部分木 定义）

教材讲解 — 競技プログラミングの鉄則 第 9 章

• 9.5 树上 DFS（B65 Road to Promotion Hard 解说）
• 9.6 Union-Find + 逆向处理（B66 Typhoon 解说）

系统练习 — 競技プログラミングの鉄則

• B61 Influencer（图基本统计）
• B62 Print a Path（路径输出）
• B65 Road to Promotion Hard（树上 DP）
• B66 Typhoon（逆序并查集）【例题】

实战练习 — 競プロ典型 90 問

• 003 Longest Circular Road（★4，树的直径）【例题】
• 039 Tree Distance（★5，换根 DP）【例题】
• 035 Preserve Connectivity（★7，虚树）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化