o55_mwisot

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
vector <int> g[N];
int dp[N][2];
int w[N];

int dfs(int u, int p){
    dp[u][1] = w[u];
    for(auto v: g[u]){
        if(v == p) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main(){

    int n;
    scanf("%d", &n);

    for(int i=1;i<=n;i++)
        scanf("%d", &w[i]);

    for(int i=1;i<=n-1;i++){
        int u, v;
        scanf("%d %d", &u, &v);
        u ++, v ++;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 1);

    printf("%d", max(dp[1][0], dp[1][1]));

    return 0;
}