题解 | 没有上司的舞会

#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <vector>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> w(n+5);
    rep(i,1,n) cin >> w[i];
    vector<int> fa(n+5);
    vector<vector<int>> a(n+5);
    rep(i,1,n-1) {
        int x,y; cin >> x >> y;
        a[x].push_back(y);
        fa[y] = x;
    }
    int root = -1;
    rep(i,1,n) if(fa[i] == 0) root = i;
    auto f = vector(n+5, vector(2, INT_MIN));
    f[root][0] = 0;
    f[root][1] = w[root];
    function<void(int)> dfs = [&](int x) -> void {
        // cerr << x << endl;
        f[x][0] = 0;
        f[x][1] = w[x];
        for(auto v : a[x]) {
            dfs(v);
            f[x][0] += max(f[v][0], f[v][1]);
            f[x][1] += max(0, f[v][0]);
        }
    };
    dfs(root);
    int ans = INT_MIN;
    cout << max(f[root][0], f[root][1]);
    // cout << ans << endl;
    
}
// 64 位输出请用 printf("%lld")