DP 系列（五）：树形 DP

本讲定位：前四讲的 DP 都发生在序列上。本讲把舞台换成树——你会发现树反而是最适合 DP 的结构：每棵子树都是一个天然的子问题，DFS 的回溯顺序就是天然的填表顺序。学完本讲，“在树上选点/选边/分配资源”这一大类问题都有了统一的解法框架。

前置知识：专题一（依赖决定顺序）、专题三（背包，第 5 节用到）；树的存储（邻接表）与 DFS。

标注 ⭐ 的小节为进阶内容。

1. 为什么树和 DP 是天作之合

回忆专题一的核心原则：转移用到谁，谁就必须先算完。序列上我们靠”下标从小到大”保证这一点；树上呢？

任选一个点作根，每个结点 $u$ 的子树就是一个独立的小世界。如果状态定义成”$u$ 的子树内部的答案”，那么 $f[u]$ 只依赖它的孩子 $f[v_1], f[v_2], \ldots$——而 DFS 恰好在回溯到 $u$ 之前，已经把所有孩子递归算完了。也就是说：

树形 DP = 状态挂在”子树”上 + 按 DFS 后序（先孩子后父亲）转移。

它本质上就是专题一的记忆化搜索，而且树上无环、每个点只会被访问一次，连 vis 数组都不需要。

代码骨架（本讲所有题共用）：

void dfs(int u, int fa) {
    初始化 f[u]（只考虑 u 自己）
    for (u 的每个邻居 v) {
        if (v == fa) continue;   // 无向存树，防止走回头路
        dfs(v, u);               // 先把子树 v 算完
        用 f[v] 更新 f[u];        // 合并孩子的答案
    }
}

树用无向图方式存（每条边存两个方向），DFS 时带上父结点参数防回头——这比”只存父到子的有向边”更通用，因为很多题不告诉你谁是根。

2. 例题一：最大子树和（洛谷 P1122）

题意：$n \le 1.6 \times 10^4$ 个结点的树，点有权值（可负）。选出一个非空连通块，使权值和最大。

样例：权值 -1 -1 -1 1 1 1 0，边 1-4, 2-5, 3-6, 4-7, 5-7, 6-7 → 答案 3（选 $\{4,5,6,7\}$）。

这是专题二”最大子段和”的树上版。序列上我们用”以 $i$ 结尾”固定接口；树上，连通块的接口是什么？——它总有一个最高点（离根最近的点）。以最高点来分类：

$$ f[u] = \text{在 } u \text{ 的子树内、包含 } u \text{ 的连通块的最大权值和} $$

包含 $u$ 的连通块 = $u$ 自己，加上若干个孩子方向的”包含 $v$ 的连通块”（要连通，必须经过 $v$ 接入）。每个孩子的贡献 $f[v]$ 是正的才要，是负的就整块不选：

$$ f[u] = w_u + \sum_{v \in \text{son}(u)} \max\big(f[v],\ 0\big) $$

答案是 $\max_u f[u]$（最优连通块的最高点可能是任何结点）。

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

int n, w[16005], f[16005];   // f[u]：包含 u 的、完全落在 u 子树内的连通块的最大权值和
vector<int> g[16005];
int ans = INT_MIN;

void dfs(int u, int fa) {
    f[u] = w[u];
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);                    // 先算完子树（后序）
        f[u] += max(f[v], 0);         // 子树的连通块是正贡献才接上
    }
    ans = max(ans, f[u]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}