30pts 求调

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 6e3 + 5;
vector<int> g[maxn];
int a[maxn];
int dp[maxn][2];
int n;
bool vis[maxn];
bool vis2[maxn][2];
int dfs (int u, bool k, int fa) { // k 开关
    if (vis2[u][k]) {
        return dp[u][k];
    }
    if (k) {
        dp[u][k] = a[u];
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa) continue;
            k = !k;
            dp[u][k] += dfs(v, k, u);
            k = !k;
        }
    }
    else {
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa) continue;
            k = !k;
            int tmp1 = dfs(v, k, u);
            k = !k;
            int tmp2 = dfs(v, k, u);
            dp[u][k] += max(tmp1, tmp2);
        }
    }
    vis2[u][k] = 1;
    return dp[u][k];
}
int main () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        vis[u] = 1;
    }
    int pt = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            pt = i;
            break;
        }
    }
    cout << max(dfs(pt, 0, -1), dfs(pt, 1, -1));
    return 0;
}