[poj 2342]简单树dp

题目链接：http://poj.org/problem?id=2342

dp[i][0/1]表示以i为根的子树，选或不选根，所能得到的最大rating和。

显然

dp[i][0]=∑max(dp[son][0],dp[son][1])

dp[i][1]=val[i]+∑dp[son][0]

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

const int maxn=6005;
int v[maxn];
int p[maxn];
vector<int> G[maxn];
int dp[maxn][2];

void dfs(int u)
{
    dp[u][0]=0;
    dp[u][1]=v[u];
    for (int i=0;i<G[u].size();i++)
    {
        dfs(G[u][i]);
        dp[u][0]+=max(dp[G[u][i]][0],dp[G[u][i]][1]);
        dp[u][1]+=dp[G[u][i]][0];
    }
}

int main()
{
    int n;
    while (scanf("%d",&n) && n)
    {
        memset(p,-1,sizeof(p));
        for (int i=1;i<=n;i++) G[i].clear();
        for (int i=1;i<=n;i++) scanf("%d",&v[i]);
        for (int i=1;i<=n-1;i++)
        {
            int u,fa;
            scanf("%d%d",&u,&fa);
            p[u]=fa;
            G[fa].push_back(u);
        }
        int root;
        for (int i=1;i<=n;i++) if (p[i]==-1) root=i;
        dfs(root);
        printf("%d
",max(dp[root][0],dp[root][1]));
    }
    return 0;
}