树形dp | 野生开发者

树形dp就是在树的结构上用动态规划，主要用DFS。

1	dp[i][j][0/1]，其中i指以i为根的子树，j指在以i为根的子树中选择j个子节点，0表示不选这个节点，1表示选择这个节点。有时候j或0/1这一维可以压掉。

基本方程：

选择节点类

1 2	dp[i][0] = dp[j][1] dp[i][1] = max/min(dp[j][0], dp[j][1])

树形背包类

1 2	dp[v][k] = dp[u][k] + val dp[u][k] = max(dp[u][k], dp[v][k-1])

入门题1：没有上司的舞会

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 6005;
int n, root, r[maxn], f[maxn][2], v[maxn];  //f记录快乐指数总和；v表示visited，用于找root；r存储每个人的快乐指数
vector<int>s[maxn];
void dp(int x){
    f[x][0] = 0;
    f[x][1] = r[x];
    for(int i = 0; i < s[x].size(); i++){
        int t = s[x][i];
        dp(t);                             //dfs
        f[x][0] += max(f[t][0], f[t][1]);  //上司没来，直接下属想来就来
        f[x][1] += f[t][0];                //上司来了，直接下属一定不来
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> r[i];
    int l, k;
    memset(v, 0, sizeof(v));
    for(int i = 1; i <= n-1; i++){
        cin >> l >> k;
        s[k].push_back(l);
        v[l] = 1;
    }
    for(int i = 1; i <= n; i++)
        if(!v[i]){
            root = i;
            break;
        }
    dp(root);
    cout << max(f[root][0], f[root][1]) << endl;
    return 0;
}

参考资料