总结 树形DP P1352 【没有上司的舞会】

[没有上司的舞会](https://www.luogu.org/problemnew/show/P1352) 这是一道树形DP的模板题，树形DP的探索从这里开始。 因为这不是一棵二叉树，所以我们要用链表模拟向量来存图，并用fa数组来存储各个结点的父亲，以直接找到树的根结点。 依据题意，我们用r数组存储快乐程度的最大值，并用f数组存当第i个结点状态为j时快乐程度最大是多少。 同时，因为要快乐程度最大，所以不掺杂负数，这个题选不选负数是无后效性的，所以负数都不选。 当做DP时，通过DFS函数深搜遍历，根据儿子（们）的状态回溯到自己的状态，这样才能从上一步的最优解推下来。树形DP的基础思想就是这样。 ```cpp #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; } ```