题解 | 没有上司的舞会

#include <iostream>
#include <cstring>


using namespace std;

const int N = 2e5 + 10;
int h[N],e[N],ne[N],idx;

int w[N];

int dp[N][2];

bool has_parent[N];

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

}


void dfs(int root){
    dp[root][1] = w[root];
    dp[root][0] = 0;

    for(int i = h[root];i != -1;i = ne[i]){
        int t = e[i];
        dfs(t);
        dp[root][1] += dp[t][0];
        dp[root][0] += max(dp[t][1],dp[t][0]);
    }
}

int main(){

    int n;
    cin>>n;

    for(int i = 1;i <= n;i++){
        cin>>w[i];
    }
    memset(h, -1, sizeof h);
    for(int i = 0;i < n - 1;i++){
        int boss,emp;
        cin>>boss>>emp;
        add(boss,emp);
        has_parent[emp] = true;

    }
    int root = -1;
    for(int i = 1;i <= n;i++){
        if(!has_parent[i]){
            root = i;
            break;
        }
    }

    dfs(root);


    cout<<max(dp[root][1],dp[root][0]);

    return 0;
}