题解 | 没有上司的舞会

树形动态规划

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
const int MAXN=2e5+5;

vector<int>son[MAXN];
int w[MAXN];
ll dp[MAXN][2];
void dfs(int u){
    dp[u][1]=w[u];
    dp[u][0]=0;
    for(int v:son[u]){
        dfs(v);
        dp[u][1]+=dp[v][0];
        dp[u][0]+=max(dp[v][0],dp[v][1]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    vector<int>dad(n+1,0);
    for(int i=0;i<n-1;i++){
        int k,l;
        cin>>k>>l;
        son[k].push_back(l);
        dad[l]=k;
    }
    int root=1;
    while(dad[root]!=0)root=dad[root];
    dfs(root);
    cout<<max(dp[root][0],dp[root][1])<<endl;
}