树形dp

还有一天半
不知道学什么好了
心情起伏波动极大

没有上司的舞会

• 题意：给定一棵树，每个点有快乐值，父亲和儿子不能同时存在，求最大快乐值。

首先分析父节点和子节点的关系
\(f[i][0]\)表示结点i不选，\(f[i][1]\)表示选
父节点影响自己点

对于父节点x的每条边i：
\(dp[x][0] = max(dp[i][0], dp[i][1])\)
\(dp[x][1] = dp[i][0]\)

所以我们递归到叶子结点，回溯+dp即可

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a[6005];
int n, dp[6005][2], v[6005], w[6005], root ;

void dfs(int x){
    dp[x][0] = 0;
    dp[x][1] = w[x];
    for(int i = 0; i < a[x].size(); i++){
        int y = a[x][i];
        dfs(y);
        dp[x][0] += max(dp[y][1], dp[y][0]);
        dp[x][1] += dp[y][0]; 
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        v[x] = 1; //x has a father 
        a[y].push_back(x); // x is a son of y
    }
    // find the root
    for(int i = 1; i <= n; i++){
        if(!v[i]) root = i;
    } 
    dfs(root);
    cout << max(dp[root][0], dp[root][1]);
    return 0;
}

树形dp

原文：https://www.cnblogs.com/hnoi/p/11856342.html