记录编号	250773	评测结果	AAAAAAAAAA
题目名称	游戏内测	最终得分	100
用户昵称	bhiaibogf	是否通过	通过
代码语言	C++	运行时间	2.177 s
提交时间	2016-04-15 21:00:15	内存使用	13.66 MiB

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> PII;
const int MAXN=(5*1e5+5);
int val[MAXN];
vector<PII> f[MAXN];
vector<int> g[MAXN];
int read(){
	int r=0;char c;
	while(!isdigit(c=getchar()));
	while(r=r*10+c-'0',isdigit(c=getchar()));
	return r;
}
 
bool cmp(const PII &a,const PII &b){
	return max(a.first,a.second+2+b.first)<max(b.first,b.second+2+a.first);
}//先去a更优
 
void Add(){
	int u=read(),v=read();
	g[u].push_back(v);
	g[v].push_back(u);
}void Init(){
	int n=read();
	for(int i=1;i<=n;i++) val[i]=read();
	for(int i=1;i<n;i++) Add();
}
 
PII F(int u,int p){
	int ans=val[u];
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==p) continue;
		f[u].push_back(F(v,u));
	}
	if(!f[u].size()) return make_pair(ans,0);
	sort(f[u].begin(),f[u].end(),cmp);
	int d=0;
	for(int i=0;i<f[u].size();i++){
		ans=max(ans,d+f[u][i].first+1);
		d+=f[u][i].second+2;
	}
	return make_pair(ans,d);
}
 
int main(){
#ifdef bhiaibogf
	freopen("in.in","r",stdin);
#else
	freopen("gamebeta.in","r",stdin);
	freopen("gamebeta.out","w",stdout);
#endif
	int __size__ = 20 << 20; // 20MB
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	Init();
	PII ans=F(1,-1);
	printf("%d\n",max(ans.first,val[1]+ans.second));
	return 0;
}