P1352 没有上司的舞会

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 6005;

int n;
int w[MAXN];
vector<int> child[MAXN];
int f0[MAXN], f1[MAXN];   // f0: 不邀请 u；f1: 邀请 u

void dfs(int u) {
    f0[u] = 0;
    f1[u] = w[u];
    for (int v : child[u]) {
        dfs(v);
        f0[u] += max(0, max(f0[v], f1[v]));
        f1[u] += f0[v];
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    vector<bool> hasBoss(n + 1, false);
    for (int i = 1; i < n; i++) {
        int l, k;
        cin >> l >> k;
        child[k].push_back(l);
        hasBoss[l] = true;
    }
    int root = 1;
    for (int i = 1; i <= n; i++) {
        if (!hasBoss[i]) { root = i; break; }
    }
    dfs(root);
    cout << max(f0[root], f1[root]) << '\n';
    return 0;
}