#include <fstream>
#include <vector>
#include <string.h>
using namespace std;

int N, val[16010],MAX[16010]; vector<int> graf[16010]; bool vizitat[16010];
ifstream in("asmax.in");
ofstream out("asmax.out");
void dfs(int nod){
    if (!vizitat[nod]){
        vizitat[nod]=1;
        int i,add=val[nod];;
        for (i=0; i<graf[nod].size(); i++) dfs(graf[nod][i]);

        for (i=0; i<graf[nod].size(); i++) if (MAX[graf[nod][i]]>0) add+=MAX[graf[nod][i]];



         for (i=0; i<=N+2; i++) out << MAX[i] << " ";
         out << "\n";
    }
}
int main(){

    in >> N;
    int i,x,y;
    for (i=1; i<=N; i++) in >> val[i];
     memset(graf,0,sizeof(graf));;
    for (i=0; i<N; i++){
        in >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    memset(vizitat,0,sizeof(vizitat));
    memset(MAX,0,sizeof(MAX));
    dfs(1);
    int max_sum=-(1<<30);
    for (i=1; i<=N; i++) { out << MAX[i] << " ";  if (MAX[i]>max_sum) max_sum=MAX[i];}
    out << "\n";
    out << max_sum;
    return 0;
}