#include <iostream>
#include <fstream>
using namespace std;
#define N 32002
ifstream in("berarii2.in");
ofstream out("berarii2.out");
int xd[N];
int g[N];
int a[N], b[N], c[N];
bool v[N];
int q[N];
int nr=0,k=0;
void add(int x, int y){
    a[++k]=y;
    b[k]=c[x];
    c[x]=k;
}
int main(){
    int n,i,x,y,m=-1000*N/2;
    cin>>n;
    for(i=1; i<=n; ++i)
        cin>>xd[i];
    for(i=1; i<n; ++i){
        cin>>x>>y;
        add(x,y);
        add(y,x);
        ++g[x];
        ++g[y];
    }
    int u=-1, p=0,st;
    for(i=1; i<=n; ++i)
        if(g[i]==1)
            q[++u]=i, v[i]=1;
    while(p<=u){
        i=q[p++];
        st=c[i];
        cout<<i<<":\n";
        while(st){cout<<a[st]<<"\n";
            if(!v[a[st]]){
                q[++u]=a[st];
                v[a[st]]=1;
                //if(xd[i]>=0)
                 //   xd[a[st]]+=xd[i];
                //m=max(m,xd[a[st]]);
            }
            if(xd[i]>=0)
                xd[a[st]]+=xd[i];
            m=max(m,xd[a[st]]);
            st=b[st];
        }
        cout<<m<<"\n\n";
    }
    cout<<m;
    return 0;
}