洛谷 P1352 没有上司的舞会 题解【树形DP】

   这是一道树形DP的模板题，树形DP的探索从这里开始。

   因为这不是一棵二叉树，所以我们要用链表模拟向量来存图，并用fa数组来存储各个结点的父亲，以直接找到树的根结点。

   依据题意，我们用r数组存储快乐程度的最大值，并用f数组存当第i个结点状态为j时快乐程度最大是多少。

   同时，因为要快乐程度最大，所以不掺杂负数，这个题选不选负数是无后效性的，所以负数尽可能不选。

   当做DP时，通过DFS函数深搜遍历，根据儿子（们）的状态回溯到自己的状态，这样才能从上一步的最优解推下来。树形DP的基础思想就是这样。

Code：

#include<cstdio>
#include<cstring>
int max(int x,int y){return x>y?x:y;}
struct node
{
    int data;
    node *next;
    node()
    {
        next=NULL;
    }
};
node head[6005],*tail[6005];
int r[6005],f[6005][2];//f[i][0]表示自己不去，f[i][1]表示自己去
int fa[6005];
void dfs(int x)
{
    node *root=&head[x];
    while(root->next!=NULL)
    {
        root=root->next;
        dfs(root->data);
        f[x][0]+=max(0,f[root->data][1]);
        f[x][1]+=max(0,f[root->data][0]);
    }
    f[x][1]+=max(0,r[x]);
    return ;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        head[i].data=i;
        tail[i]=&head[i];
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&r[i]);
    int a,b;
    scanf("%d%d",&a,&b);
    while(a!=0&&b!=0)
    {
        fa[a]=b;
        node *t=new node();
        t->data=a;
        tail[b]->next=t;
        tail[b]=t;
        scanf("%d%d",&a,&b);
    }
    int k=1;
    while(fa[k]!=k)
        k++;
    dfs(k);
    printf("%d\n",max(f[k][1],f[k][0]));
    return 0;
}