学步园

/*
 * poj2342 AC
 * 典型的树状DP。
 * dp[i][0]表示员工i参加舞会的最大值，dp[i][1]表示员工i不参加舞会的最大值。
 *
 * dp[i][0] = max(dfs(son[i],1));
 * i参加则i的儿子结点一定不能参加。
 * dp[i][1] = max(dfs(son[i],0),dfs(son[i],1));
 * i不参加则i的儿子结点可参加，也可以不参加。
 *
 * 最初居然考虑错误，实在不应该,此题和摘苹果那题还是有区别的，每个结点要记录两个
 * 状态，而非一个。
 * */
#include<cstdio>
#include<algorithm>
#include<memory.h>
#define MIN (-(1<<30))
using namespace std;

int tree[6005],conv[6005],head[6005],next[6005],num[6005],root;
long dp[6005][2];
long dfs(int x,int state)
{
    if(dp[x][state]!=MIN) return dp[x][state];

    long i;
    if(num[x]==0)
    {
        dp[x][0] = conv[x],dp[x][1] = 0;
        return dp[x][state];
    }

    if(state)
    {
        for(dp[x][state]=0,i=head[x];i;i=next[i])
            dp[x][state] += max(dfs(tree[i],0),dfs(tree[i],1));
    }else
    {
        for(dp[x][state]=conv[x],i=head[x];i;i=next[i])
            dp[x][state] += dfs(tree[i],1);
    }
    return dp[x][state];
}

int main()
{
    int n,i,j,k,tot;
//    FILE* fin;
//    fin = fopen("d.in","r");
//    fscanf(fin,"%d",&n);
    scanf("%d",&n);

    for(i=1;i<=n;i++)
    {
        dp[i][0] = dp[i][1] = MIN;
        scanf("%d",&conv[i]);
//        fscanf(fin,"%d",&conv[i]);
    }
    memset(num,0,sizeof(num));
    for(root=(1+n)*n/2,tot=0,i=1;i<=n-1;i++)
    {
        scanf("%d%d",&j,&k);
//        fscanf(fin,"%d%d",&j,&k);
        tree[++tot] = j,next[tot] = head[k],head[k] = tot,num[k]++,root -= j;
    }
    long ans;
    ans = max(dfs(root,0),dfs(root,1));
    printf("%ld\n",ans);
    return 0;
}