poj 2342(树形DP)

///分析：dp[i][0] 代表第i个人不去能够获得的最大愉悦值,以i为根的子树能够获得的最大愉悦值
///      dp[i][1] 代表第i个人去了能够获得的最大愉悦值,以i为根的子树能够获得的最大愉悦值
///dp[i][1] = dp[i][1] + dp[j][0] j为i的孩子
///dp[i][0] = dp[i][0] + max(dp[j][0],dp[j][1])
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 6005
using namespace std;

int dp[N][2];
int indgree[N];
int isroot[N];
struct Edge{
    int u,v,next;
}edge[N];
int head[N];
void addEdge(int u,int v,int &k){
    edge[k].u = u,edge[k].v = v;
    edge[k].next = head[u],head[u]=k++;
}
void dfs(int u){
    for(int k = head[u];k!=-1;k=edge[k].next){
        int v = edge[k].v;
        dfs(v);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(head,-1,sizeof(head));
        memset(indgree,0,sizeof(indgree));
        memset(isroot,0,sizeof(isroot));
        for(int i=1;i<=n;i++){
            scanf("%d",&dp[i][1]);
        }
        int tot=0;
        int u,v;
        while(scanf("%d%d",&v,&u),u+v){
            addEdge(u,v,tot);
            isroot[u]=1;
            indgree[v]++;
        }
        int root;
        for(int i=1;i<=n;i++){
            if(indgree[i]==0) root = i;
        }
        dfs(root);
        //printf("%d\n",root);
        printf("%d\n",max(dp[root][0],dp[root][1]));
    }
    return 0;
}