트리 dp Anniversary party(HDU1520)

제목: 나무 한 그루를 주면 (상하급 관계) 각 노드마다 하나의 권한이 있다. 일부 노드를 선택하여 이 노드들이 임의로 개점도 직접적인 상하급 관계가 아닌 것을 만족시켜야 한다. 얻을 수 있는 최대 권한은 얼마나 됩니까?
분석: 각 점에 대해 두 가지 상태를 선택하거나 선택하지 않으면 상태 수조 dp[u][0]와 dp[u][1]로 현재 u노드가 뿌리 노드의 서브트리로서 변점 u를 선택하면 상태 방정식은 다음과 같다.
dp[u][1]=max(dp[u][1],dp[u][1]+dp[v][0]);선택하지 않으면 방정식은 dp[u][0]=dp[u][0]+max(dp[v][0], dp[v][1])이다.
프로그램:

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"algorithm"
#include"math.h"
#define M 6009
#define inf 0x3f3f3f3f
#define eps 1e-10
using namespace std;
struct node
{
    int u,v,w,next;
}edge[M*2];
int t,head[M],p[M],dp[M][3],degree[M];
void init()
{
    t=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v)
{
    edge[t].u=u;
    edge[t].v=v;
    edge[t].next=head[u];
    head[u]=t++;
}
void dfs(int u,int f)
{
    dp[u][0]=0;
    dp[u][1]=p[u];
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f)continue;
        dfs(v,f);
        dp[u][0]=dp[u][0]+max(dp[v][0],dp[v][1]);
        dp[u][1]=max(dp[u][1],dp[u][1]+dp[v][0]);
    }
}
int main()
{
    int n,i,a,b;
    while(scanf("%d",&n)!=-1)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&p[i]);
        init();
        memset(degree,0,sizeof(degree));
        while(1)
        {
            scanf("%d%d",&a,&b);
            if(!a&&!b)break;
            add(b,a);
            degree[a]++;
        }
        int root;
        for(i=1;i<=n;i++)
        {
            if(degree[i]==0)
            {
                root=i;
                break;
            }
        }
        dfs(root,root);
        //for(i=1;i<=n;i++)
            //printf("%d: %d %d
",i,dp[i][0],dp[i][1]);
        printf("%d
",max(dp[root][0],dp[root][1]));
    }
    return 0;
}