#include <stdio.h>
#include <list>
#include <climits>

/* Nume fisiere intrare/iesire */
#define FIN  "asmax.in"
#define FOUT "asmax.out"

#define MIN(a,b) ((a<b)?(a):(b))
#define MAX(a,b) ((a>b)?(a):(b))

/* Numar maxim de intrari */
#define NMAX 16001

/* fisiere */
FILE *in, *out;

/* numarul de noduri */
int N;

/* arbore reprezentat prin liste de adiacenta */
std::list<int> graph[NMAX];

/* valorile din noduri */
long values[NMAX];

/* vector de dinamica */
long dinamica[NMAX];

void DFS(int node){
    if(graph[node].empty()){
        dinamica[node] = values[node];
        return;
    }

    int sum = 0;
    for(std::list<int>::iterator it = graph[node].begin(); it != graph[node].end(); ++it){
        int neigh = *it;
        DFS(neigh);
        if(sum + dinamica[neigh] > dinamica[node] && sum + dinamica[neigh] > sum) sum += dinamica[neigh];
    }

    dinamica[node] = sum;
}

void solve(){
    for(int i=1; i < N; i++) dinamica[i] = LONG_MIN/2;
    DFS(1);

    printf("SOLUTIE: %d\n", dinamica[1]);
}

int main(){
    /* deschidere fisiere */
    in = fopen(FIN, "rt");
    out = fopen(FOUT, "wt");
    if(!in || !out) return 1;

    fscanf(in, "%d", &N);
    for(int i=1; i <= N; i++) fscanf(in, "%li", &values[i]);

    for(int i=1; i < N; i++){
        int a,b;
        fscanf(in, "%d%d", &a, &b);

        int s = MIN(a,b);
        int d = MAX(a,b);
        graph[s].push_back(d);
    }

    for(int i=1; i <= N; i++){
        printf("%li ", values[i]);
    }
    printf("\n");
    for(int i=1; i <= N; i++){
        printf("[%d]:", i);
        for(std::list<int>::iterator it = graph[i].begin(); it != graph[i].end(); ++it){
            printf("%d ", *it);
        }
        printf("\n");
    }

    solve();

    /* inchidere fisiere */
    fclose(in);
    fclose(out);
    return 0;
}