#include <fstream.h>
#define N 16100
ifstream fin("asmax.in");
ofstream fout("asmax.out");
struct nod {int info;nod *urm;};
int n,tati[N],radacina;
nod *fii[N],*q;
long long s[N],v[N];
void citire()
{
fin>>n;
int i;
for(i=1;i<=n;i++)
	{
	fin>>v[i];
	tati[i]=0;
	}
int a,b;
for(i=1;i<n;i++)
	{
	fin>>a>>b;
	q=new nod;
	q->info=b;
	q->urm=fii[a];
	fii[a]=q;
	tati[b]=a;
	}
for(i=1;i<=n;i++)
if(tati[i]==0)
	{
	radacina=i;
	break;
	}
}
int max(int a,int b)
{
if(a>b) return a;
return b;
}

void progdin(int k)
{
int sum=0;
nod *p;
p=fii[k];
int i;
	while(p)
	{
	progdin(p->info);
	p=p->urm;
	}
s[k]=v[k];
p=fii[k];
while (p)
 {
  s[k]=s[k]+max(0,s[p->info]);
  p=p->urm;
 }
}
int main()
{
int max,i,j;
nod *p;
citire();
for(i=1;i<=n;i++)
{
p=fii[i];
if(p)
{fout<<i<<')';
while(p)
{fout<<p->info<<' ';
p=p->urm;}
fout<<endl;
}
}
progdin(radacina);
for(i=1;i<=n;i++)
fout<<s[i]<<' ';
fout<<endl;
max=s[1];
for(i=2;i<=n;i++)
if (max<=s[i])
max=s[i];
fout<<max<<'\n';
return 0;
}