记录编号	251006	评测结果	AAAAAAAAAA
题目名称	游戏内测	最终得分	100
用户昵称	咸鱼二号	是否通过	通过
代码语言	C++	运行时间	0.733 s
提交时间	2016-04-16 17:21:42	内存使用	38.94 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<cstdlib>
#include<iomanip>	//cout<<setiosflags(ios::fixed)<<setprecision(2);
#include<ctime> //double a=(double)clock();	cout<<a<<endl;
#include<vector>
#include<queue>
using namespace std;
const int maxn=500010;
inline int read(){
	int x=0,ff=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ff=-1; ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
	return ff*x;
}
inline long long mymax(long long xx,long long yy)
{if(xx>yy)return xx;return yy;}
int N,C[maxn],t1,t2;
int lin[maxn],len=0;
struct edge{
	int y,next;
}e[maxn<<1];
inline void insert(int xx,int yy){
	e[++len].next=lin[xx];
	lin[xx]=len;
	e[len].y=yy;
}
long long f[maxn],d[maxn];
inline bool mycmp(const int &x,const int &y)
{return mymax(f[x],d[x]+2+f[y])<mymax(f[y],d[y]+2+f[x]);}
/*void dfs(int x,int fa){
	if(f[x]!=-1)return;f[x]=C[x];
	for(int i=lin[x];i;i=e[i].next)
		if(e[i].y!=fa){
			dfs(e[i].y,x);
			d[x]+=d[e[i].y]+2;
		}
	vector<int>box;
	for(int i=lin[x];i;i=e[i].next)
		if(e[i].y!=fa)
			box.push_back(e[i].y);
	sort(box.begin(),box.end(),mycmp);
	int siz=box.size(),temp=0;
	for(int i=0;i<siz;i++){
		f[x]=mymax(f[x],f[box[i]]+temp+1);
		temp+=d[box[i]]+2;
	}
}*/
int stack[maxn],prev[maxn],top=0,now;
bool vis[maxn];
int t[maxn],cnt,temp;
void dfs(int x,int fa){
	stack[++top]=x,prev[top]=fa;
	while(top){
		loop:
		now=top;
		for(int i=lin[stack[now]];i;i=e[i].next)
			if(e[i].y!=prev[now]&&(!vis[e[i].y])){
				stack[++top]=e[i].y,prev[top]=stack[now];
				vis[e[i].y]=1;
				goto loop;
			}
		f[stack[now]]=C[stack[now]];
		cnt=0;
		for(int i=lin[stack[now]];i;i=e[i].next)
			if(e[i].y!=prev[now]){
				d[stack[now]]+=d[e[i].y]+2;
				t[++cnt]=e[i].y;
			}
		sort(t+1,t+1+cnt,mycmp);
		temp=0;
		for(int i=1;i<=cnt;i++){
			f[stack[now]]=mymax(f[stack[now]],f[t[i]]+temp+1);
			temp+=d[t[i]]+2;
		}
		top--;
	}
}
int main(){
	freopen("gamebeta.in","r",stdin);
	freopen("gamebeta.out","w",stdout);
	N=read();
	for(int i=1;i<=N;i++)
		C[i]=read();
	for(int i=1;i<N;i++){
		t1=read(),t2=read();
		insert(t1,t2),insert(t2,t1);
	}
	memset(f,-1,sizeof(f));
	dfs(1,0);
	cout<<mymax(f[1],d[1]+C[1])<<endl;
	return 0;
}