#include <iostream>
#include <cstdio>
#include <fstream>
#define MINIMUM -30000;
using namespace std;
short int st[1000],v[1000],t[1000];
short int k,n,i,m,c=0;
bool ev,as;
bool oprire(bool as,bool ev)
{
    bool stop=false;
    if (!as) stop=true;
    else if ((as) && (ev)) stop=true;
    return(stop);
}
bool sub_arbore(short int t[100],short int st[100],short int k)
{
    bool legatura=false;
    for(short int j=1;j<=k-1;++j)
    if (t[st[k]]==st[j])
    {
        legatura=true;
        break;
    }
    return(legatura);
}
void init(short int st[100],short int k)
{
    st[k]=0;
}
void succesor(bool &as,short int st[100],short int k)
{
    if (st[k]<n-m+k)
    {
        st[k]=st[k]+1;
        as=true;
    }
    else as=false;
}
void valid(bool &ev,short int st[100],short int k)
{
    ev=true;
    for(short int j=1;j<=k-1;++j)
     if (st[j]==st[k]) {ev=false;}
     if (ev) if (k>1) if (!sub_arbore(t,st,k)) ev=false;
}
bool solutie(short int k,short int m)
{
    bool sol=false;
    if (k==m) sol=true;
    return(sol);
}
int suma(short int v[100],short int st[100],short int k)
{
    int ss=0;
    for(short int j=1;j<=k;++j)
     ss=ss+v[st[j]];
     return(ss);
}
int main()
{
     bool pozitiv=true;
     int s=0,x,y;
     freopen("asmax.in","r",stdin);
     freopen("asmax.out","w",stdout);
     scanf("%d",&n);
     for(i=1;i<=n;++i)
     {scanf("%d",&v[i]); s=s+v[i]; if (v[i]<0) pozitiv=false;}
      if (pozitiv); //printf("%d",s);
      else
      {
          for(i=1;i<=n-1;++i)
          {
              scanf("%d %d",&x,&y);
              if  (x>y)t[x]=y;
               else t[y]=x;
          }
         short int maxiim=MINIMUM;
         for(i=1;i<=n;++i)
         {
             m=i;
             k=1;
             init(st,k);
             while (k>0)
             {
                 do
                 {
                     succesor(as,st,k);
                     if (as) valid(ev,st,k);
                 }
                 while(!oprire(as,ev));
                 if (as)
                 {
                     if (solutie(k,m)) {if (suma(v,st,k)>maxiim) maxiim=suma(v,st,k);}
                      else {++k;init(st,k);}
                 }
                 else --k;
             }
         }
          printf("%d",maxiim);
      }

    return 0;
}