#include <stdio.h>
#include <stdlib.h>
#define MAXN 16000
#define INF 1000000000

int v[1+MAXN], start[1+MAXN], next[1+MAXN], d[1+MAXN];

int D(int nod){
    if(d[nod]==-INF){
        d[nod]=v[nod];
        int i=start[nod];
        while(i!=0){
            if(D(i)>0)
                d[nod]+=D(i);
            i=next[i];
        }
    }
    return d[nod];
}

int main(){
    int n;
    FILE*fi,*fo;
    fi=fopen("asmax.in","r");
    fo=fopen("asmax.out","w");
    fscanf(fi,"%d", &n);
    for(int i=1;i<=n;i++){
        fscanf(fi,"%d", &v[i]);
        d[i]=-INF;
    }
    for(int i=1;i<n;i++){
        int a, b;
        fscanf(fi,"%d%d", &a, &b);
        next[b]=start[a];
        start[a]=b;
    }
    int maxim=-INF;
    for(int i=1;i<=n;i++){
        if(D(i)>maxim)
            maxim=D(i);
        printf("%d %d\n", i, D(i));
    }
    fprintf(fo,"%d", maxim);
    fclose(fi);
    fclose(fo);
    return 0;
}