rt,不吸氧过不去
/*Quark and Tree*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
int sum[maxn];
ll f[maxn];
int deg[maxn];
int w[maxn];
ll rec = 0;
int head[maxn];
int tot = 0;
ll ans = -1e9;
struct Edge{
int next,point;
}edge[maxn*2];
inline void add(int x,int y){
edge[++tot].next = head[x];
edge[tot].point = y;
head[x] = tot;
deg[y]++;
}
inline void Dfs(int x,int fa){
sum[x] = w[x];
for(register int i = head[x]; i ; i = edge[i].next){
int y = edge[i].point;
if(y == fa) continue;
Dfs(y,x);
sum[x] += sum[y];
}
rec += sum[x];
}
int Min[maxn][3];
inline void TreeDp(int x,int rt,int fa) {
f[x] = sum[x];
for(register int i = head[x]; i ; i = edge[i].next){
int y = edge[i].point;
if(y == fa) continue;
TreeDp(y,rt,x);
if(!Min[x][1] || f[y] < f[Min[x][1]]){
Min[x][2] = Min[x][1];
Min[x][1] = y;
}
else if(!Min[x][2] || f[y] < f[Min[x][2]]){
Min[x][2] = y;
}
}
if(x != rt){
if(f[Min[x][1]] < 0)
f[x] += f[Min[x][1]];
}
else
f[x] += f[Min[x][1]] + f[Min[x][2]];
}
inline void Dfs1(int x,int fa){
if(deg[x] > 1){
ans = max(ans,rec - f[x]);
}
ll oldrec = rec;
int min1,min2;
ll oldx,oldy;int oldsumx;
for(register int i = head[x]; i; i = edge[i].next){
int y = edge[i].point;
if(y == fa) continue;
oldx = f[x],oldy = f[y],oldsumx = sum[x];
min1 = Min[x][1],min2 = Min[x][2];
//memcpy(old_ymin,Min[y],sizeof(Min[y]));
rec -= (sum[x] + sum[y]);
sum[x] -= sum[y]; sum[y] += sum[x];
rec += (sum[x] + sum[y]) ;
f[x] = sum[x],f[y] = sum[y];
if(Min[x][1] == y){
Min[x][1] = Min[x][2];
}
if(f[Min[x][1]] < 0)
f[x] += f[Min[x][1]] ;
if(!Min[y][1] || f[x] < f[Min[y][1]]){
Min[y][2] = Min[y][1];
Min[y][1] = x;
}
else if(!Min[y][2] || f[x] < f[Min[y][2]]){
Min[y][2] = x;
}
f[y] += f[Min[y][1]] + f[Min[y][2]];
Dfs1(y,x);
f[x] = oldx,f[y] = oldy,sum[x] = oldsumx;
Min[x][1] = min1,Min[x][2] = min2;
rec = oldrec;
}
}
inline int read(){
char ch = getchar();
int f = 1,x = 0;
while(ch < '0' || ch > '9') f = (ch == '-')?-1:f,ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48),ch = getchar();
return x * f;
}
int main()
{
int n;
cin >> n;
for(register int i = 1; i <= n; ++i){
w[i] = read();
}
for(register int i = 1; i < n; ++i){
int x,y;
x = read(),y = read();
add(x,y); add(y,x);
}
Dfs(1,0);
TreeDp(1,1,0);
Dfs1(1,0);
printf("%lld\n",ans);
return 0;
}