记录编号	256086	评测结果	AAAAAAAAAA
题目名称	[POJ 2342] 猴腮雷	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.288 s
提交时间	2016-04-29 11:20:01	内存使用	0.43 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=6006;
int n,f[maxn][2],father[maxn],a[maxn],fe[maxn]={0};
void Dfs(int x);
int main()
{
	freopen("monk.in","r",stdin);
	freopen("monk.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&f[i][0]);
	int x,y;
	bool t=1;
	int root=0;
	while(scanf("%d%d",&x,&y)==2 && x+y>0)
	{
		father[x]=y;
		if(root==x || t)
		{
			root=y;
			t=0;
		}
	}
	Dfs(root);
	int ans=max(f[root][0],f[root][1]);
	printf("%d",ans);
}
void Dfs(int x)
{
	fe[x]=1;
	for(int i=1;i<=n;i++)
	{
		if(!fe[i] && father[i]==x)
		{
			Dfs(i);
			f[x][0]+=f[i][1];
			f[x][1]+=max(f[i][0],f[i][1]);
		}
	}
}