树形 DPCSP-S

💡 核心思想

树形 DP 是在树结构上进行的动态规划，通常以"某个节点为根的子树"来定义状态。由于树没有环，天然的递归结构使得 DP 转移非常自然。经典问题：树的直径、最大独立集、树的重心等。

🎯 直觉理解

树形 DP 就是"在树上做动态规划"：树天然是递归结构——每个节点的答案由它的子树答案组合而来。典型做法：DFS 后序遍历，算完所有儿子再算父亲。

经典例子没有上司的舞会：每个职员要么去要么不去。$dp[u][0/1]$ 表示 u 去/不去时子树的最大欢乐值——u 不去时儿子可去可不去，u 去时儿子都不能去。

套路：状态通常带"选/不选"之类的 0/1，转移时枚举儿子逐个合并，复杂度 $O(n)$（每条边只遍历一次）。树形 DP 的关键是想清楚"儿子给父亲贡献什么"。

📝 算法流程

1. 建树（邻接表存边）
2. 从任意节点开始 DFS
3. 后序遍历：先处理子树，再处理当前节点
4. 状态转移：根据子节点的 dp 值更新当前节点

$$dp[u][0/1] \text{：节点 } u \text{ 不选/选 时子树的最优值}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
// 树的最大独立集（没有上司的舞会）
vector g[6005];
int r[6005], dp[6005][2];
bool hasFather[6005];
void dfs(int u) {
    dp[u][0] = 0;
    dp[u][1] = r[u]; // 选 u
    for (int v : g[u]) {
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]); // 不选 u，子节点可选可不选
        dp[u][1] += dp[v][0];                  // 选 u，子节点不能选
    }
}
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> r[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v; // v 是 u 的上司
        g[v].push_back(u);
        hasFather[u] = true;
    }
    int root = 1;
    while (hasFather[root]) root++;
    dfs(root);
    cout << max(dp[root][0], dp[root][1]) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目