树形DP

从题意可以得出：

• 如果选了当前节点u，那么他所有的儿子都不能选
• 如果不选当前节点u，那么他所有的儿子既可以选，也可以不选

$ 时间复杂度O(N)，空间复杂度O(N) $

参考文献

算法基础课

AC代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 6010;

int n;
int w[N];
int f[N][2];
int h[N], e[N], ne[N], idx;//邻接表
bool st[N];//记录当前节点是否有父亲

void add(int a ,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u){
    f[u][0] = 0;//不选
    f[u][1] = w[u];//选

    for (int p = h[u] ; p != -1 ; p = ne[p]){
        int s = e[p];
        dfs(s);
        f[u][1] += f[s][0];
        f[u][0] += max(f[s][0], f[s][1]);
    }
}

int main(){
    //读入
    cin >> n;
    for (int i = 1 ; i <= n ; i ++) cin >> w[i];
    memset(h, -1, sizeof h);
    for (int i = 1 ; i < n ; i ++) {
        int a, b;
        cin >> a >> b;
        add(b, a);
        st[a] = true;
    }

    //找根节点
    int root = 1;
    while (st[root] == true) root ++;

    //树形DP
    dfs(root);

    //输出答案
    cout << max(f[root][0], f[root][1]) << endl;

    return 0;
}