DepTree 3.0

#include<bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
int n,r[N];
struct Node{
    int fa;
    vector<int> chd;
};
Node g[N];
int rt;
int dp[N][N];
void dfs(int u){
    if(g[u].chd.size() == 0){
        dp[u][0] = 0,dp[u][1] = r[u];
    }else {
        dp[u][0] = 0,dp[u][1] = r[u];
        for(int i = 0;i < g[u].chd.size();i++){
            int v = g[u].chd[i];
            dfs(v);
            dp[u][0] += max(dp[v][0],dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
}
int main(){
    cin >>n;
    for(int i = 1;i <= n;i++) cin >> r[i];
    for(int i = 1;i < n;i++){
        int l,k;
        cin >> l >> k;
        g[l].fa = k;
        g[k].chd.push_back(l);
    }
    rt = 1;
    while(g[rt].fa != 0){
        rt = g[rt].fa;
    }
    dfs(rt);
    cout << max(dp[rt][0],dp[rt][1]) << endl;
    return 0;
}