记录编号	251136	评测结果	AAAAAAAAAA
题目名称	游戏内测	最终得分	100
用户昵称	lxtgogogo	是否通过	通过
代码语言	C++	运行时间	1.903 s
提交时间	2016-04-16 21:56:51	内存使用	25.11 MiB

/*
Language: c++
Author: lxtgogogo
Date: 2016.04.15
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
using namespace std;
inline int read(){
	int x=0;bool f=true;char ch=getchar();
	while(ch>'9' || ch<'0')	{if(ch=='-'){f=false;}ch=getchar();}
	while(ch>='0' && ch<='9')	{x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return f?x:-x;
}
const int r=500010;
int n=0,ans=0;
int w[r]={};
int son[r]={},fa[r]={},size[r]={};
long long cost[r]={};//time
long long f[r]={};//the less time to update

struct hehe{
	int y,next;
}e[r*2];
int linkk[r]={},len=0;

bool mycmp(int a,int b){
	bool flag=false;
	if(max(f[a],cost[a]+2+f[b])<max(f[b],cost[b]+2+f[a]))	flag=true;
	return flag;
}
inline int max(long long a,long long b){if(a>b){return a;}return b;}
inline void insert(int a,int b){
	e[++len].next=linkk[a];linkk[a]=len;e[len].y=b;
}
void init(){
	n=read();
	for(int i=1;i<=n;i++)	w[i]=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		insert(x,y);
		insert(y,x);
	}
}
void dfs(int k){
	size[k]=1;
	for(int i=linkk[k];i;i=e[i].next)
		if(e[i].y!=fa[k])
		{
			fa[e[i].y]=k;
			dfs(e[i].y);
			size[k]+=size[e[i].y];
		}
	cost[k]=size[k]*2-2;
}
void dp(int k){
	int tot=0;
	for(int i=linkk[k];i;i=e[i].next)
		if(e[i].y!=fa[k])
			dp(e[i].y);
	for(int i=linkk[k];i;i=e[i].next)
		if(e[i].y!=fa[k])
			son[++tot]=e[i].y;
	sort(son+1,son+tot+1,mycmp);
	int temp=1;
	for(int i=1;i<=tot;i++)
	{
		f[k]=max(f[k],temp+f[son[i]]);
		temp+=cost[son[i]]+2;
	}
	f[k]=max(max(cost[k],w[k]),f[k]);
}
int main(){
	freopen("gamebeta.in","r",stdin);
	freopen("gamebeta.out","w",stdout);
	
	int __size__ = 20 << 20; // 20MB
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	
	init();
	dfs(1);
	dp(1);
	ans=max(cost[1]+w[1],f[1]);
	cout<<ans<<endl;
	
	fclose(stdin);fclose(stdout);
	return 0;
}