算法1

C++ 代码

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;

const int N = 6010;

bool hasF[N];
int dp[N][2], happy[N];
unordered_map<int, vector<int>> tree;

void dfs(int root){
    dp[root][1] += happy[root];
    for(auto child : tree[root]){
        dfs(child);
        dp[root][0] += max(dp[child][0], dp[child][1]);
        dp[root][1] += dp[child][0];
    }
}

int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> happy[i];
    }
    for(int i = 0; i < n - 1; i ++){
        int a, b;
        cin >> a >> b;
        tree[b].push_back(a);
        hasF[a] = true;
    }
    int root = 1;
    while(hasF[root]){
        root ++;
    }
    // cout << root << endl;
    dfs(root);
    // cout << dp[root][0] << " " << dp[root][1] << endl;
    cout << max(dp[root][0], dp[root][1]) << endl;
    return 0;
}