题解 | 没有上司的舞会

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+6;
int value[N];
int dp[N][2];
bool root[N];
vector<vector<int>>tree;
void dfs(int now){
    /*对于当前的now结点，有选和不选两种可能，不选的最大值为子结点选或者不选相加，选的最大值，为子结点不选相加*/
    for(int i:tree[now]){
        dfs(i);/*不用考虑那么多，反正你是从根结点开始的，所以你直接往下搜索即可*/
        dp[now][1]+=dp[i][0];
        dp[now][0]=max(dp[now][0]+dp[i][0],dp[now][0]+dp[i][1]);
    }
    dp[now][1]+=value[now];
}
int main(){
    int n;
    cin>>n;
    tree.resize(n+1);
    for(int i=1;i<=n;i++){cin>>value[i];dp[i][0]=0;dp[i][1]=0;}
    for(int i=1;i<n;i++){
        int l,r;
        cin>>l>>r;
        tree[l].push_back(r);
        root[r]=true;
    }
    int gen;
    for(int i=1;i<=n;i++){
        if(!root[i]){gen=i;break;}
    }
    dfs(gen);
    cout<<max(dp[gen][1],dp[gen][0]);
    return 0;
}