树形 DPCSP-S

💡 核心思想

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

🎯 直觉理解

想象一个公司的组织架构（树形结构）。CEO 要做一个决策，他先问所有部门经理，部门经理问组长，组长问员工。信息从叶子节点一层层汇总到根节点——这就是树形 DP 的过程。

📝 算法流程

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

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

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 树的最大独立集（没有上司的舞会）
vector<int> 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;
}

⚠️ 常见坑点

📚 相关题目