rt

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int maxn=2e5+5;
struct node{
	int to,nxt;
}t[maxn<<1];
int n,tot,sum,idx=1,ans;
int f[maxn],maxs[maxn],s[maxn],a[maxn];
void add(int u,int v){
	t[++tot].to=v;
	t[tot].nxt=f[u];
	f[u]=tot;
}
void dfs1(int fa,int u){
	s[u]=a[u];
	for(int i=f[u];i;i=t[i].nxt){
		if(t[i].to==fa) continue;
		dfs1(u,t[i].to);
		s[u]+=s[t[i].to];
		maxs[u]=max(maxs[u],s[t[i].to]);
	}
	maxs[u]=max(maxs[u],sum-s[u]);
}
void dfs2(int fa,int u){
	for(int i=f[u];i;i=t[i].nxt){
		if(t[i].to==fa) continue;
		s[t[i].to]=s[u]+1;
		dfs2(u,t[i].to);
	}
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
	for(int i=1,u,v;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);
	dfs1(1,1);
	for(int i=2;i<=n;i++) if(maxs[i]<maxs[idx])	idx=i;
	s[idx]=0;
	dfs2(idx,idx);
	for(int i=1;i<=n;i++) ans+=s[i]*a[i];
	cout<<ans<<endl;
	return 0;
}