P1352 没有上司的舞会

#include<bits/stdc++.h>
using namespace std;
class DP_on_tree{
public:
	int n;
	int a[6001];
	int vis[6001];
	int f[6001][3];
	vector < int > e[6001];
	void DP(int x)
	{
		f[x][1]=a[x];
		for(int i=0; i<e[x].size(); i++)
		{
			int y=e[x][i];
			DP(y);
			f[x][0]+=max(f[y][1],f[y][0]);
			f[x][1]+=f[y][0];
		}
		return;
	}
	void Main()
	{
		memset(a,0,sizeof(a));
		memset(vis,0,sizeof(vis));
		memset(f,0,sizeof(f));
		scanf("%d",&n);
		for(int i=1; i<=n; i++)
		{
			scanf("%d",&a[i]);
		}
		for(int i=1; i<n; i++)
		{
			int x,y;
			cin>>x>>y;
			vis[x]=1;
			e[y].push_back(x);
		}
		int x=0;
		while(vis[++x]);
		DP(x);
		printf("%d\n",max(f[x][0],f[x][1]));
	}
};
int main()
{
	DP_on_tree x;
	x.Main();
}