POJ 2342 （树形dp入门）

//树形dp，现在才开始看，先敲个水题入个门吧，这个题很简单，知道树dp的概念大概就能做出来

//我们用dp[root][2]代表当前节点这个人是否参加当前聚会的方法数，dp[i][0]代表不参加加,dp[i][1]代表参加，那么dp[i][0]+=max(dp[j][0],dp[j][1]),dp[i][1]+=dp[j][0],其中j为i的下属，及儿子节点，用fa数组表示父亲和儿子的关系即可.

//树形dp入门，ac代码如下。

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int  maxn = 6005;
int dp[maxn][2];
int fa[maxn];
bool vis[maxn];
int n;
void Tree_dp(int root)
{
    vis[root] = 1;
    for(int i=1; i<=n; i++)
    {
        if(!vis[i]&&fa[i]==root)
        {
            Tree_dp(i);//递归调用子节点
            dp[root][1] += dp[i][0];//上司来，下属不来
            dp[root][0] += max(dp[i][0],dp[i][1]);//上司不来，下属优先选择最优方案
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));
        memset(fa,0,sizeof(fa));
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++)scanf("%d",&dp[i][1]);
        int a,b,root=0;
        //找根节点
        bool flag=1;
        while(scanf("%d %d",&a,&b),a||b)
        {
            fa[a] = b;
            if(root==a||flag)
            {
                root = b;
            }
        }
        //回溯找根节点
        while(fa[root])
        {
            root = fa[root];
        }
        Tree_dp(root);
        int ans = max(dp[root][0],dp[root][1]);
        printf("%d\n",ans);
    }
    return 0;
}