学步园

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 6000+50;
int dp[maxn][2];
bool vis[maxn];
struct node
{
    int fa;
    vector<int> ch;
};
node p[maxn];
void dfs(int cur)
{
    vis[cur]=1;
    int s=p[cur].ch.size();
    for(int i=0;i<s;i++)
    {
        int ch=p[cur].ch[i];
        if(!vis[ch])
        {
            dfs(ch);
            dp[cur][1]+=dp[ch][0];
            dp[cur][0]+=max(dp[ch][1],dp[ch][0]);
        }
    }
}
int main()
{
    int n,a,b,root;
    while(~scanf("%d",&n))
    {
        memset(p,0,sizeof(p));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&dp[i][1]);
            dp[i][0]=0;
        }
        while(~scanf("%d%d",&a,&b)&&(a||b))
        {
            p[a].fa=b;
            p[b].ch.push_back(a);
        }
        root=1;
        for(int i=1;i<=n;i++)
        {
            if(!p[i].fa)
            {
                root=i;
                break;
            }
        }
        dfs(root);
        printf("%d\n",max(dp[root][0],dp[root][1]));
    }
    return 0;
}