AYITACM2016省赛第三周 L - Anniversary party（树形dp）

　　　　dp[c][1]+=dp[t][0];      //c去,则t必不能去

　　上司不去，下级去或者不去：
　　　　dp[c][0]+=max(dp[t][0],dp[t][1]);      //c不去，取t去或不去的最大值

和深搜很像，也就是用的深搜。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>g[10001];
int dp[10001][3],root[10001];
void dfs(int c)
{
    int i,t;
    for(i=0;i<(int)g[c].size();i++)
    {
        t=g[c][i];//节点的孩子
        dfs(t);//把孩子作为节点再搜索它的孩子
        dp[c][1]+=dp[t][0];//如果双亲去，孩子就不能去
        dp[c][0]+=max(dp[t][0],dp[t][1]);//如果双亲不去，就选择孩子中欢乐值大的去
    }
}
int main()
{
    int n,i,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&dp[i][1]);//输入第i个人的活跃度
            root[i]=i;//初始化每个节点都是根节点，也是并查集的初始化
            g[i].clear();//清空容器
        }
        while(scanf("%d%d",&a,&b)&&a+b)
        {
            g[b].push_back(a);//把数据存入容器中
            root[a]=b;  //a的根节点为b
        }
        int beg;
        for(i=1;i<=n;i++)
            if(root[i]==i)//如果根节点是本身，说明就是树的根节点
         {
             beg=i;
            break;
        }
        dfs(beg);//搜索这棵树
        printf("%d\n",max(dp[beg][0],dp[beg][1]));//输出最终的欢乐值
    }
return 0;
}