记录编号	240889	评测结果	AAAAAAAAAA
题目名称	修剪花卉	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-03-24 07:03:41	内存使用	0.67 MiB

#include<cstdio>
#include<vector>
using namespace std;
const int SIZEN=16010;
typedef long long LL;
int N;
vector<int> s[SIZEN];
int pos[SIZEN];
LL f[SIZEN]={0};
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&pos[i]);
	int fr,to;
	for(int i=1;i<N;i++) 
	{
		scanf("%d%d",&fr,&to);
		s[fr].push_back(to);
		s[to].push_back(fr);
	}
}
LL ans=0;
void DP(int x,int fa)
{
	f[x]=pos[x];
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i];
		if(v==fa) continue;
		DP(v,x);
		f[x]=max(f[x],f[x]+f[v]);
	}
	ans=max(ans,f[x]);
}
void work()
{
	DP(1,0);
	printf("%d\n",ans);
}
int main()
{
	freopen("makeup.in","r",stdin);
	freopen("makeup.out","w",stdout);
	read();
	work();
	return 0;
}