记录编号	188170	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	赵日天	是否通过	通过
代码语言	C++	运行时间	0.265 s
提交时间	2015-09-21 21:44:30	内存使用	3.73 MiB

#include <cstdio>
//----------------------------------------------------
inline int Max(int num1,int num2) { return num1>num2?num1:num2; }
//----------------------------------------------------
int  n;
int  a,b;
int  i,j;

int  T;
int  w[100010];
int  l[200010];
int  t[200010];

int  top,tai;
int  far[100010];
int  sta[100010];

int  o[100010];
int  x[100010];
//----------------------------------------------------
int  main( )
{
	freopen( "profitz.in"  , "r" , stdin  );
	freopen( "profitz.out" , "w" , stdout );
	scanf("%d",&n);
	for (i=1; i<=n; i++) scanf("%d",&o[i]);
	for (i=1; i< n; i++)
	{
		scanf("%d%d",&a,&b);
		l[++T]=w[a]; w[a]=T; t[T]=b;
		l[++T]=w[b]; w[b]=T; t[T]=a;
	}
	
	//-- s1
	sta[0]=far[1]=1;
	for (top=tai=0; top<=tai; top++)
	for (i=w[sta[top]]; i; i=l[i])
	if (!far[t[i]])
	{
		far[t[i]]=sta[top];
		sta[++tai]=t[i];
	}
	//-- s2
	for (tai++; --tai; )
	{
		o[far[sta[tai]]]+=x[sta[tai]];
		x[far[sta[tai]]]+=Max(o[sta[tai]],x[sta[tai]]);
	}
	//-- s3
	printf("%d",Max(o[1],x[1]));
}