📖 第 8.3 章 ⏱️ 约 60 分钟 🎯 Gold / 困难

第 8.3 章：树形 DP 与换根

📝 前置要求： 本章需要第 5.4 章（二叉树与树算法：遍历、LCA）、第 5.5 章（并查集）、第 6.1～6.2 章（DP 基础）及第 8.2 章（DAG DP）。阅读树形 DP 前，必须理解 DFS 后序遍历。

树形 DP 在有根树上运行动态规划，以每棵子树作为子问题。这是 USACO Gold 中最重要的技术之一，几乎出现在所有 Gold/Platinum 树题中。

换根技术（Rerooting）将树形 DP 扩展到能在 O(N) 时间内处理以每个节点为根的查询——无需对每个根单独运行一次 DFS。

学习目标：

编写基于子树的树形 DP 模板
计算树的直径、最长路径、子树和
运用换根技术，以 O(N) 时间回答"以某节点为根时的结果"
识别 USACO Gold 树题中的树形 DP 模式

8.3.0 为什么树适合 DP？

有根树本质上是一个 DAG（边从根指向子节点）。这意味着：

无环： DP 的转移方向始终是从父到子（无回溯）
自然子问题： 以 v 为根的子树构成一个完整、独立的子问题
简洁递推： dp[v] 只依赖 dp[v 的子节点]

核心模式： 后序 DFS——先处理子节点，再处理父节点。

树：          DFS 后序：        DP 顺序：
    1             4, 5, 2       先计算 dp[4]、dp[5]，
   / \            6, 3          再用它们计算 dp[2]
  2   3           2, 3
 / \   \           1             dp[v] 在所有子节点后才计算
4   5   6                        → 父节点可以直接使用子节点的 dp 值

8.3.1 树形 DP 模板

标准树形 DP 模板：带父节点参数的 DFS，避免回溯。

📄 标准树形 DP 模板：带父节点参数的 DFS，避免回溯。

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

const int MAXN = 100001;
vector<int> adj[MAXN];
int dp[MAXN];  // 根据问题定义 dp 数组

void dfs(int u, int parent) {
    // 初始化 dp[u]（基础情况：叶节点）
    dp[u] = /* 初始值 */ 0;

    for (int v : adj[u]) {
        if (v == parent) continue;  // 不回溯到父节点

        dfs(v, u);  // ← 先对子节点递归（后序）

        // 现在 dp[v] 已计算好 → 用它更新 dp[u]
        dp[u] = /* 合并 dp[u] 和 dp[v] */;
    }
}

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

    dfs(0, -1);  // 以顶点 0 为根，无父节点

    cout << /* 用 dp 值计算答案 */ "\n";
    return 0;
}

8.3.2 经典树形 DP 问题

问题 1：子树大小

sz[v] = 以 v 为根的子树中节点数。

int sz[MAXN];

void dfs(int u, int par) {
    sz[u] = 1;  // 计入 u 自身
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        sz[u] += sz[v];  // 加上子节点的子树大小
    }
}

问题 2：子树最大深度

depth[v] = 从 v 到其子树中任意叶节点的最大距离。

int depth[MAXN];

void dfs(int u, int par) {
    depth[u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        depth[u] = max(depth[u], depth[v] + 1);  // 经过 v 延伸路径
    }
}

问题 3：树的直径

树的直径是任意两节点之间的最长路径。核心思路：最长路径要么经过根节点，要么完全在某棵子树内。

方法一：两次 DFS（最简洁）

📄 C++ 完整代码

int farthest_node, max_dist;

void dfs_farthest(int u, int par, int dist) {
    if (dist > max_dist) {
        max_dist = dist;
        farthest_node = u;
    }
    for (int v : adj[u]) {
        if (v != par)
            dfs_farthest(v, u, dist + 1);
    }
}

int treeDiameter(int n) {
    // 第 1 步：找直径的一个端点（离节点 0 最远的节点）
    max_dist = 0;
    dfs_farthest(0, -1, 0);
    int endpoint1 = farthest_node;

    // 第 2 步：找另一个端点（离 endpoint1 最远的节点）
    max_dist = 0;
    dfs_farthest(endpoint1, -1, 0);

    return max_dist;  // 直径长度
}

方法二：DP（更通用）

📄 C++ 完整代码

int diameter = 0;
int max_down[MAXN];  // max_down[v] = 从 v 向下延伸的最长路径

void dfs(int u, int par) {
    max_down[u] = 0;
    vector<int> child_depths;

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        child_depths.push_back(max_down[v] + 1);
    }

    // 经过 u 的直径 = 最长的两条向下路径之和
    sort(child_depths.rbegin(), child_depths.rend());
    if (child_depths.size() >= 1) max_down[u] = child_depths[0];
    if (child_depths.size() >= 2) {
        diameter = max(diameter, child_depths[0] + child_depths[1]);
    }
    diameter = max(diameter, max_down[u]);
}

问题 4：树上最大独立集

选出尽可能多的节点，使得任意两个被选节点均不相邻（不通过一条边相连）。

📄 选出尽可能多的节点，使得任意两个被选节点均不相邻（不通过一条边相连）。

int dp[MAXN][2];
// dp[v][0] = v 未被选中时，v 子树中的最大节点数
// dp[v][1] = v 被选中时，v 子树中的最大节点数

void dfs(int u, int par) {
    dp[u][0] = 0;
    dp[u][1] = 1;  // v 自身被选中

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        dp[u][0] += max(dp[v][0], dp[v][1]);  // v 未选：子节点可选可不选
        dp[u][1] += dp[v][0];                  // v 已选：子节点必须不选
    }
}

// 答案 = max(dp[root][0], dp[root][1])

8.3.3 换根技术

问题： 对树中每个顶点 v，计算以 v 为根时的某个值。朴素做法需要 N 次 DFS → O(N²)。换根技术只需两次 DFS：O(N)。

核心思路：

DFS 1（向下传）： 计算 down[v] = 以原始根为根时，v 子树的答案
DFS 2（向上传）： 计算 up[v] = 树中"v 子树以外的部分"对应的答案
v 为根的最终答案： 合并 down[v] 和 up[v]

换根模板：距离之和

问题： 对每个顶点 v，求 v 到其他所有顶点的距离之和。输出 N 个值。

这是经典 Gold 题。核心递推关系：

若已知 dist_sum[root]（根到所有顶点的距离之和），则对根的子节点 c：

dist_sum[c] = dist_sum[root] - sz[c] + (n - sz[c])
            = dist_sum[root] + (n - 2 * sz[c])

原因： 从根移动到 c 时，c 子树中的 sz[c] 个节点各近了 1，子树外的 (n - sz[c]) 个节点各远了 1。

📄 C++ 完整代码

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

const int MAXN = 100001;
vector<int> adj[MAXN];
long long sz[MAXN];      // 子树大小
long long down[MAXN];    // v 到其子树中所有节点的距离之和
long long ans[MAXN];     // 最终答案：v 到所有节点的距离之和

int n;

// DFS 1：计算 sz[] 和 down[]（向下传递距离和）
void dfs1(int u, int par) {
    sz[u] = 1;
    down[u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        down[u] += down[v] + sz[v];  // v 子树中的所有节点多走了一步
    }
}

// DFS 2：向下传播答案（换根）
void dfs2(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;
        // ans[v] = ans[u] - sz[v] + (n - sz[v])
        //        = ans[u] + (n - 2 * sz[v])
        ans[v] = ans[u] + (n - 2 * sz[v]);
        dfs2(v, u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    dfs1(0, -1);
    ans[0] = down[0];  // 从根 0 出发到其他所有节点的距离之和
    dfs2(0, -1);

    for (int i = 0; i < n; i++)
        cout << ans[i] << "\n";

    return 0;
}

复杂度： O(N)——两次 DFS，各 O(N)。

换根的直觉理解

🤔 为什么有效？

可以理解为将"视角"从父节点转移到子节点。当我们把根从 u 移动到其子节点 v 时：

v 子树中的节点：每个近了 1 → 减去 sz[v]

不在 v 子树中的节点：每个远了 1 → 加上 (n - sz[v])

净变化：+(n - sz[v]) - sz[v] = +(n - 2·sz[v])

8.3.4 换根的一般模式

换根技术可以推广到许多问题。关键是找到：

原始根定下来后，down[v] 表示什么？
将根从父节点 u "换"到子节点 v 时，答案如何变化？
从 ans[u] 计算 ans[v] 的公式是什么？

一般结构：

DFS 1（后序）：
    down[v] = combine(down[child_1], down[child_2], ..., sz[v])

DFS 2（前序）：
    ans[v] = combine(down[v], up[v])
    对 v 的每个子节点 c：
        up[c] = f(ans[v], down[c], sz[c], n)
        // "up[c]" 是 c 子树之外所有内容的贡献

8.3.4b 换根示例 2：每个节点的最大距离

问题： 对每个顶点 v，求 v 到任意其他顶点的最大距离（v 的"离心率"）。输出 N 个值。

这比距离之和更难，因为 max 操作不像 sum 那样可以干净地分解。

核心思路： 对每个顶点 v，最远的顶点要么：

在 v 的子树中（由 DFS 1 中的 down[] 计算）
经过 v 的父节点可达（由 DFS 2 中向下传播的 up[] 计算）

📄 2. 经过 v 的父节点可达（由 DFS 2 中向下传播的 `up[]` 计算）

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

const int MAXN = 100001;
vector<int> adj[MAXN];
int n;

int down[MAXN];   // down[v] = 向下进入 v 子树的最大深度
int up[MAXN];     // up[v]   = 经 v 的父节点向上的最大深度
int ans[MAXN];    // ans[v]  = v 的离心率（到任意节点的最大距离）

// DFS 1：计算 down[]（v 子树中的最大深度）
void dfs1(int u, int par) {
    down[u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs1(v, u);
        down[u] = max(down[u], down[v] + 1);
    }
}

// DFS 2：向下传播 up[]（往"上方"走的最远距离是多少？）
// up[v] = 从 v 经过父节点能到达的最大距离
void dfs2(int u, int par) {
    ans[u] = max(down[u], up[u]);

    // 计算 up[子节点] 时，需要 u 的第一深和第二深子树
    // （若子节点恰好是最深路径上的节点，则用第二深；否则用最深）
    int best1 = -1, best2 = -1;
    int best1_child = -1;

    for (int v : adj[u]) {
        if (v == par) continue;
        int d = down[v] + 1;
        if (d > best1) { best2 = best1; best1 = d; best1_child = v; }
        else if (d > best2) { best2 = d; }
    }

    for (int v : adj[u]) {
        if (v == par) continue;
        // up[v] = 从 u 向上走或进入兄弟子树的最大距离
        int sibling_best = (v == best1_child) ? best2 : best1;
        int through_parent = up[u] + 1;  // 经 u 的父节点向上，再向下

        up[v] = max(through_parent, (sibling_best >= 0 ? sibling_best + 1 : 0));

        dfs2(v, u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    dfs1(0, -1);
    up[0] = 0;   // 根节点没有父节点
    dfs2(0, -1);

    for (int i = 0; i < n; i++)
        cout << ans[i] << "\n";

    return 0;
}

💡 关键技巧： 分别追踪最深的两棵子树。如果我们要计算 up[] 的子节点恰好是最深的子树，就用第二深的作为兄弟贡献。

8.3.4c 树背包（子树选择 DP）

问题： 给定有根树，每个顶点 v 有重量 w[v] 和价值 b[v]。选取顶点使总重量 ≤ W，约束条件：若选取 v，则必须同时选取其父节点（从根出发的连通子集）。最大化总价值。

这是经典的树背包（群组背包在树上的变体）。

朴素 O(N²W) 方法

📄 查看代码：朴素 O(N²W) 方法

// dp[v][j] = 从 v 的子树中恰好选取 j 重量（v 包含其中）时的最大价值
// 基础：dp[v][w[v]] = b[v]（只选 v，子树中无其他节点）

const int MAXN = 501, MAXW = 501;
int dp[MAXN][MAXW];
int sz[MAXN];    // 子树 DP 中已使用的"容量"
int w[MAXN], b[MAXN];

void dfs(int u, int par) {
    fill(dp[u], dp[u] + MAXW, -1);  // -1 = 不可行
    dp[u][w[u]] = b[u];
    sz[u] = w[u];

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        // 通过背包卷积将 dp[v] 合并到 dp[u]
        // 逆序处理，避免重复计数
        for (int j = min(sz[u] + sz[v], W); j >= w[u]; j--) {
            for (int k = w[v]; k <= min(j - w[u], sz[v]); k++) {
                if (dp[u][j - k] != -1 && dp[v][k] != -1) {
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
                }
            }
        }
        sz[u] = min(sz[u] + sz[v], W);
    }
}

// 答案 = max(dp[root][j]) 对 j = 0..W

为什么实际上是 O(NW)——合并分析

关键思路： 总工作量受到限制——每对来自不同子树的顶点 (u, v) 只在它们的 LCA 合并时被比较一次。由于每对比较代价为 O(1)，且每对最多被计一次，总工作量为 min(O(N²), O(NW))。

实用说明： 对于 USACO，N ≤ 300、W ≤ 300 是典型约束，O(N²W) 或 O(NW) 都很容易通过。

"从根出发的连通子集"背包模板

📄 查看代码："从根出发的连通子集"背包模板

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

const int MAXN = 305;
vector<int> adj[MAXN];
int w[MAXN], b[MAXN];
int dp[MAXN][MAXN];   // dp[v][j] = 在 v 的子树中选 j 重量（包含 v）的最大价值
int subtree_w[MAXN];  // 子树总重量

int n, W;

void dfs(int u, int par) {
    fill(dp[u], dp[u] + W + 1, 0);
    dp[u][w[u]] = b[u];
    subtree_w[u] = w[u];

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        // 将 dp[v] 合并到 dp[u]
        int cap = min(subtree_w[u] + subtree_w[v], W);
        for (int j = cap; j >= w[u]; j--) {
            for (int k = w[v]; k <= min(j - w[u], subtree_w[v]); k++) {
                if (dp[v][k] > 0)
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
        subtree_w[u] = min(subtree_w[u] + subtree_w[v], W);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> W;
    for (int i = 0; i < n; i++) cin >> w[i] >> b[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(0, -1);

    int ans = 0;
    for (int j = 0; j <= W; j++)
        ans = max(ans, dp[0][j]);

    cout << ans << "\n";
    return 0;
}

8.3.5 USACO Gold 树形 DP 题型模式

模式 1：选取子树节点

"选择部分顶点激活。激活顶点 v 的代价为 c[v]，收益为 b[v]。约束：只有父节点激活后才能激活 v。最大化净收益。"

这是"依赖背包"树形 DP：

// dp[v][j] = 从 v 的子树中选取 j 个顶点的最大收益
// 转移：通过背包合并 dp[v] 与 dp[子节点]

模式 2：树上路径查询

"对每个顶点 v，求最远顶点，或距离之和。"

换根模板——正如 8.3.3 节所示。

模式 3：树上匹配/配对

"在树上配对顶点（每对由一条路径连接）。最大化不相交的配对数。"

dp[v][0/1] = v 未被匹配（0）或已被匹配（1）时，v 子树中的最大配对数。

💡 思路陷阱

陷阱 1：换根题用 O(N²) 暴力 DFS

错误判断： "对每个节点做一次 DFS 计算它当根时的答案，O(N²) 应该够"
实际情况： N=10⁵ 时 O(N²)=10¹⁰，稳定 TLE；此类题几乎都是换根 DP 的典型形态

题目特征（三选一即触发）：
  1. "对每个节点 v，求以 v 为根时..."
  2. "输出 N 个值，每个值对应某节点当根的结果"
  3. "求使某个全局指标最小/最大的根节点"

正确：两次 DFS（dfs1 下行 + dfs2 上行）→ O(N)

识别信号： 输出 N 个值且每个值依赖"以该节点为根的某属性" → 换根 DP，而非 N 次 DFS

陷阱 2：树形 DP 中忘记 `if (v == par) continue`

错误判断： "树是无向图，从 u 出发访问邻居，DFS 会自动不走回头路"
实际情况： 无向图的邻接表中父节点也在邻居列表里，不加 par 检查会死循环/重复计数

📄 C++ 完整代码

// 错误：没有 parent 检查
void dfs(int u) {
    for (int v : adj[u]) {
        dfs(v);              // 若 u 的父节点是 v，这里会死循环！
        dp[u] += dp[v];
    }
}

// 正确：传入 parent 参数
void dfs(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;   // ← 这一行至关重要
        dfs(v, u);
        dp[u] += dp[v];
    }
}

识别信号： 树的 DFS 运行时栈溢出或结果明显偏大 → 先检查有无 parent 防回溯

陷阱 3：用单次 DFS 求"树直径"，结果错误

错误判断： "直径就是最深叶子到根的距离，单次 DFS 记录最大深度即可"
实际情况： 直径的两端点不一定经过根，单次 DFS 只算了"经过根的最长路径"

📄 Code 完整代码

树：  1
     / \
    2   3
   /     \
  4       5
  |       |
  6       7

从根 1 出发最大深度 = 3（到 6 或 7），但直径 = 6→4→2→1→3→5→7 = 6 条边
单次 DFS from root 得到 3（错），正确做法：
  方法1：两次 DFS/BFS（从任意点找最远点 A，再从 A 找最远点 B）
  方法2：树 DP，每个节点维护最深和次深子树，直径 = 全局最大的 (最深+次深)

识别信号： "树上最长路径"题 → 直径，要么两次 BFS/DFS，要么树 DP 维护双最深

⚠️ 常见错误

缺少 if (v == par) continue： 没有这个检查，DFS 会沿着边回到父节点，导致无限递归。每棵树的 DFS 都必须有这个保护。
叶节点基础情况初始化错误： 叶节点没有子节点，循环体不会执行。确保循环之前 dp[leaf] 已正确初始化。
换根的 dfs2 忘了用前序： dfs2 必须从父节点向子节点传播（自顶向下），所以 ans[u] 必须在 ans[u 的子节点] 之前计算。不要不小心用成后序。
子树和的整数溢出： 若 N = 10⁵ 且每个顶点贡献最多 N，总和可达 10¹⁰。使用 long long。
"距离之和"的差一错误： 公式 down[u] += down[v] + sz[v] 为 v 子树中的每个节点加了 sz[v]（它们各多走了一步）。理解为什么是 sz[v] 而非 sz[v]-1。

📋 章节小结

📌 核心要点

概念	说明
树形 DP	后序 DFS；dp[v] 在所有子节点之后计算；O(N)
子树大小	`sz[v] = 1 + sum(sz[子节点])`
树的直径	最长路径；两次 DFS 或追踪最深和次深子节点的 DP
最大独立集	`dp[v][0/1]` 分别对应未选/已选；经典树形 DP
换根	两次 DFS：先向下计算，再向上传播；O(N) 处理所有根
距离之和	经典换根：`ans[子节点] = ans[父节点] + n - 2*sz[子节点]`

❓ 常见问题

Q：如何判断问题是否需要换根？
A：若问题对每个顶点（以该顶点为根时）请求相同的计算——"对每个顶点，求以它为根时的 X"——那就需要换根。若只对一个固定根请求，标准树形 DP 就够了。

Q：如果边权不为 1 怎么办？
A：调整公式即可。对于带权边，若边 (u,v) 的权重为 w，则 down[u] += down[v] + sz[v] * w[u][v]。换根公式相应调整。

Q：可以用迭代 DFS 替代递归吗？
A：可以，对于大 N 更应该这样做（避免栈溢出）。用显式栈将 DFS 改为迭代，按与入栈相反的顺序处理顶点（后序）。

🔗 与后续章节的联系

第 8.4 章（欧拉游览）： 当树形 DP 本身对树上区间查询的效率不够时，欧拉游览 + BIT/线段树是首选方案。
第 8.1 章（MST）： 从一般图构建 MST 后，MST 就是一棵树，可以对其做树形 DP。
第 6.3 章（进阶 DP）： 树形 DP 是 DAG 上 DP（第 8.2 章）的特例，技术可以互相推广。

🏋️ 练习题

🟢 简单

8.3-E1. 子树查询
给定有根树，对每个顶点 v，输出其子树中的节点数。

提示

标准 sz[] 计算。sz[v] = 1 + sum(sz[子节点])。

8.3-E2. 树的直径
求 N 个顶点、单位边权的树的直径（最长路径）。

提示

两次 BFS/DFS：从任意顶点 BFS 找最远顶点 A；再从 A BFS 找最远顶点 B。A 到 B 的距离即为直径。

🟡 中等

8.3-M1. 最大独立集 （USACO 风格）
给定 N 个顶点的树，每个顶点有一个值。选出总价值最大的顶点子集，使得任意两个被选顶点之间没有边相连。

提示

经典 dp[v][0/1]。dp[v][1] = val[v] + sum(dp[子节点][0])；dp[v][0] = sum(max(dp[子节点][0], dp[子节点][1]))。

8.3-M2. 距离之和 （LeetCode 834 / USACO Gold 风格）
对树中每个顶点，求它到所有其他顶点的距离之和。输出 N 个值。

提示

使用 8.3.3 节的换根模板。两次 DFS，总复杂度 O(N)。

🔴 困难

8.3-H1. 牛聚集 （USACO 2019 February Gold）
N 头奶牛在一棵树上。每头牛有"幸福值"。当牛的父节点离开时，该牛变得更幸福。模拟移除操作，最大化总幸福值。（简化版：找到移除奶牛的顺序，使每次移除时的累积幸福值之和最大。）

提示

建模为树形 DP：对每棵子树计算按最优顺序移除顶点的"收益"。通过换根来回答所有可能起始顶点的情况。

🏆 挑战

8.3-C1. 树背包 （困难）
给定 N 个顶点的有根树，每个顶点 v 有重量 w[v] 和价值 b[v]。选取顶点子集 S，总重量 ≤ W，且若 v ∈ S 则 parent(v) ∈ S（从根出发的连通子集）。最大化总价值。

提示

dp[v][j] = 从 v 的子树（包含 v）中恰好选取 j 重量的最大价值。通过卷积风格的背包合并子节点。用仔细的合并策略可以达到 O(N·W)——关键思路是每对顶点只被比较一次，因此总复杂度通过 DFS 顺序达到 O(N·W)。

C++ 竞赛编程：USACO 学习指南