题目描述

blablabla

样例

blablabla

没想到写完直接一遍过了，开心特此发个题解

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 6010;

vector<int> g[N];
int val[N];
int memo[N][2];//0 代表不选根节点 1 代表选根节点
bool fa[N];//用来找到根

int dfs(int root, int select){
    if(memo[root][select] != -1) return memo[root][select];
    int ans = 0;
    if(select == 0) 
        for(auto t : g[root])
            ans += max(dfs(t, 0), dfs(t, 1));
    else{
        ans += val[root];
        for(auto t : g[root])
            ans += dfs(t, 0);
    }
    return memo[root][select] = ans;
}

int main(){
    int n;cin >> n;
    for(int i = 1;i <= n;++i) cin >> val[i];
    for(int i = 1;i <= n-1;++i){
        int a, b; cin >> a >> b;
        g[b].push_back(a);
        fa[a] = true;
    }
    int root = 1;
    while(fa[root]) ++root;
    memset(memo, -1, sizeof memo);
    cout << max(dfs(root, 0), dfs(root, 1)) << endl;
    return 0;
}