cv1380(树形dp)

题目链接

分析：
填坑
f[i][1]表示选i
f[i][0] 表示不选i
设y是i的儿子
很简单，选爸爸就不能选儿子
f[i][1]+=f[y][0]
不选爸爸，儿子的状态无所谓
f[i][0]+=max(f[y][0],f[y][1])

tip

递归求解，所以在进行dp的时候
当前状态的所有后继状态一定是计算好了的，
我们不用考虑孙子的状态，只看爸爸和儿子就好了

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

struct node{
    int x,y,nxt;
};
node way[6010];
int a[6010],n,st[6010],tot=0;
bool son[6010];
int f[6010][2];

void add(int u,int w)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
}

void doit(int now)
{
    int i,j,ans=0;
    for (i=st[now];i;i=way[i].nxt)
    {
        int y=way[i].y;
        doit(y);
        f[now][0]+=max(f[y][0],f[y][1]);
        f[now][1]+=f[y][0]; 
    }
    f[now][1]+=a[now];
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    int u,w;
    scanf("%d%d",&u,&w);
    while (u&&w)
    {
        add(w,u);
        son[u]=1;
        scanf("%d%d",&u,&w);
    }
    int root;
    for (int i=1;i<=n;i++) 
        if (!son[i]){
            root=i;
            break;
        }
    doit(root);
    printf("%d",max(f[root][0],f[root][1]));
    return 0;
}