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;
}