记录编号	251621	评测结果	AAAAAAAAAA
题目名称	游戏内测	最终得分	100
用户昵称	WAHT	是否通过	通过
代码语言	C++	运行时间	1.015 s
提交时间	2016-04-18 14:39:25	内存使用	59.44 MiB

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=500010;
#define ll long long
struct my
{
	int y,next;
}e[maxn<<2];
int linkk[maxn],len;
void insert(int xx,int yy)
{	e[++len].next=linkk[xx],e[linkk[xx]=len].y=yy;	}
struct two
{
	ll s,v,id;
}q[maxn];
bool cm(two x,two y){	return max(x.v,x.s+y.v)<max(y.v,y.s+x.v);	}
ll f[maxn],d[maxn];
ll a[maxn],n;
int Q[maxn],fa[maxn],linkk2[maxn];
void dfs()
{
	Q[len=1]=1;
	while(len)
	{
		int tn=Q[len];
		bool vis=1;
		for(int i=linkk[tn];i;i=e[i].next)
		{
			int to=e[i].y;
			if(to==fa[tn])	continue;
			fa[to]=tn;
			Q[++len]=to;
			vis=0;
			linkk[tn]=e[i].next;
			break;
		}
		if(vis)
		{
			int num=0;
			for(int i=linkk2[tn];i;i=e[i].next)
			{
				int to=e[i].y;
				if(to==fa[tn])	continue;
				q[++num].v=f[to],q[num].s=d[to]+2;
			}
			sort(q+1,q+1+num,cm);
			f[tn]=a[tn];
			ll sum=0;
			for(int i=1;i<=num;i++)
			{	
				f[tn]=max(f[tn],sum+q[i].v+1);
				sum+=q[i].s;
			}
			len--;
			d[fa[tn]]+=d[tn]+2;
		}
	}
}
int main()
{
	freopen("gamebeta.in","r",stdin);
	freopen("gamebeta.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		insert(a,b);	insert(b,a);
	}
	for(int i=1;i<=n;i++)	linkk2[i]=linkk[i];
	dfs();
	cout<<max(a[1]+d[1],f[1])<<endl;
}