动态规划-树形DP

4FGR2025-11-202025-11-20

参考资料：树形 DP - OI Wiki

树形DP

树形 DP，即在树上进行的DP。由于树固有的递归性质，一般通过递归DFS（或 BFS）进行

基础

P1352 没有上司的舞会 - 洛谷

某大学有 $n$ 个职员，编号为 $1\ldots n$。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

不妨设 $f(i,0/1)$ 表示以 $i$ 为根的子树当其根节点的值 取/不取 的最优解（ $0$ 表示 $i$ 不去舞会，反之要去）

对于每个状态，都存在两种决策（以下 $x$ 为 $i$ 的所有儿子）

上司不参加舞会时，下属可以参加，也可以不参加，是否参加取决于所能产生的最大快乐值，因此有

\[ f(i,0) = \sum max(f(x,0),f(x,1)) \]

上司参加舞会时，下属只能不参加，但下属的下属则未必

\[ f(i,1) = a_i + \sum f(x,0) \]

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4;
long long dp[N][2];
int a[N]; //记录快乐值
int v[N]; //是否为子节点
vector<int> g[N]; //存放图

void dfs(int x){ //递归求dp
    dp[x][0] = 0;
    dp[x][1] = a[x];
    for(auto i : g[x]){
        dfs(i); //先得到dp[i][0/1]
        dp[x][0] += max(dp[i][0],dp[i][1]);
        dp[x][1] += dp[i][0];
    }
}


int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=0;i<n-1;i++){
        int l,k;
        cin >> l >> k;
        g[k].push_back(l);
        v[l] = 1;
    }
    int root;
    for(int i=1;i<=n;i++){
        if(!v[i]){
            root = i; //找到根节点
            break;
        }
    }
    dfs(root);
    cout << max(dp[root][0],dp[root][1]);
}