dp on tree

/* dp on tree */


ll n,arr[MAX];vi v[MAX];ll choto[MAX],boro[MAX],ans;

void dfs1(int s,int p = 0)
{
    choto[s] = arr[s];
    for(auto it : v[s])
    {
        if(it==p)continue;
        dfs1(it,s);
        boro[s]+=choto[it]+boro[it];
        choto[s]+=choto[it];
    }
}


void dfs2(int s,int p = 0)
{
    if(p)
        boro[s]=boro[p]+choto[p]-choto[s]-choto[s];
    if(p)
        choto[s]=choto[p];
    ans = max(ans,boro[s]);
    for(auto it : v[s])
    {
        if(it==p)continue;
        dfs2(it,s);
    }
}


int main()
{
    booster()

    cin>>n;

    for(int i = 1;i<=n;i++)cin>>arr[i];

    for(int i = 0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }

    dfs1(1);

    dfs2(1);

    cout<<ans;

    return 0;
}