树形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;
}