记录编号	531045	评测结果	AAAAAAAAAA
题目名称	没有上司的舞会	最终得分	100
用户昵称	LGLJ	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2019-05-08 17:09:06	内存使用	0.00 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cctype>
#define I inline
#define R register
#define LL long long
using namespace std;
struct EDGE
{
	int next,to;
}edge[6010];
int n;
int num[6010]={0};
int head[6010]={0},tot=0;
int ent[6010]={0},root;
int f[6010][2]={0};
I void add_edge(int u,int v)
{
	edge[++tot].next=head[u];
	edge[tot].to=v;
	head[u]=tot;
}
I int read()
{
	int x=0;
	char ch=0;
	bool w=true;
	while(!isdigit(ch)){if(ch=='-')w=false;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return w?x:-x;
}
I void dfs(int u)
{
	f[u][1]=num[u];
	for(R int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		dfs(v);
		f[u][0]=max(f[u][0],max(f[u][0]+f[v][0],f[u][0]+f[v][1]));
		f[u][1]=max(f[u][1],f[u][1]+f[v][0]);
	}
}
I int MAIN()
{
	freopen ("partyy.in","r",stdin);
	freopen ("partyy.out","w",stdout);
	n=read();
	for(R int i=1;i<=n;++i)
		num[i]=read();
	for(R int i=1,a,b;i<n;++i)
	{
		a=read(),b=read();
		add_edge(b,a);
		++ent[a];
	}
	for(R int i=1;i<=n;++i)
		if(!ent[i])
		{
			root=i;
			break;
		}
	dfs(root);
	cout<<max(f[root][0],f[root][1]);
	return 0;
}
int lglj=MAIN();
int main(){;}