记录编号	250807	评测结果	AAAAAAAAAA
题目名称	游戏内测	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	2.832 s
提交时间	2016-04-15 22:38:12	内存使用	17.95 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define N 500010
using namespace std;
ifstream in("gamebeta.in");
ofstream out("gamebeta.out");
vector<int> G[N],F[N];
int d[N],f[N],c[N];
bool vis[N]={0};
int n;
bool com(int a,int b)
{
	return max(f[a],f[b]+d[a]+2)<max(f[b],f[a]+d[b]+2);
}
void DFS(int u)
{
	int i,v;
	vis[u]=1;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!vis[v])
		{
			F[u].push_back(v);
			DFS(v);
			d[u]=d[u]+d[v]+2;
		}
	}
	if(!F[u].size())
	{
		d[u]=0;
		f[u]=c[u];
		return ;
	}
	sort(F[u].begin(),F[u].end(),com);
	int sum=0;
	for(i=0;i<F[u].size();i++)
	{
		v=F[u][i];
		f[u]=max(f[u],sum+f[v]+1);
		sum+=d[v]+2;
	}
	f[u]=max(f[u],c[u]);
}
void read()
{
	int i,u,v;
	in>>n;
	for(i=1;i<=n;i++)in>>c[i];
	for(i=1;i<n;i++)
	{
		in>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
		//out<<u<<' '<<v<<endl;
	}
	DFS(1);
}
void work()
{
	
	int ans;
	ans=max(f[1],d[1]+c[1]);
	out<<ans<<endl;
}
int main()
{
	int __size__ = 20 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	read();
	work();
	return 0;
}