树形DP之题解 P2014 【选课】
wjyyy
2018-03-04 19:39:24
【选课】这道题看上去是一道进阶版的树形DP，因为其中嵌套了一定的背包的思想
代码流程：首先建树存图，这里的处理有一个小技巧，就是如果有多个根结点，那么不容易进行DFS，所以我们构造出一个$0$结点，刚好，输入时也是用$0$来代替的，这样只用在最后输出时调用$\mathrm{[m+1]}$即可。s数组代表该结点有几个儿子，之后在DFS中更新为后代个数，p数组代表结点的权值，（图中黑色数字）
然后开始DFS，DFS的回溯是树形DP的重点以及核心。
我们DFS的搜索边界是链表的尾端，**当回溯结束后，$root$的子树已经被遍历完并处理完了。**这便是树形DP的最重要的特点。
**背包**过程中嵌套了三重循环（实际加上DFS的是四重），
首先$\mathrm {r=root->next}$枚举了$\mathrm {root}$的子树 _子树间不会互相影响，所以这些可以分开做。_ 但是$j$和$k$的顺序一定要分好，因为是相当于$01$背包，所以$k$要倒序，$j$是用来枚举$\mathrm {r->data}$即正在遍历的点的儿子个数，因为现在正在遍历的点已经被DFS过了（要不然不会退到这个$x$结点的），则它是当前状况的最优解，可以从那边转移过来。**但是$k$一定要在$j$前面，因为当$k$相同时，不同的$j$可能存在包含相同点的情况，为了避免这种情况，我们选择把k放在外面。这样$f[x][k]$就不会重复更新涉及相同的点了——举个栗子** 
```cpp
如果k循环在j里面的话，当我们更新到图中2号结点后，1号结点的f[x][k]会被更新，
在k++;后，f[x][k]在符合情况时会继续更新，这样就会导致结果出错（偏大）的情况出现
```
**背包核心：**
```cpp
while(r!=0)
{
for(int k=s[x];k>=1;k--)
for(int j=1;j<=k;j++)//j是枚举r->data的选科个数
//其中j<=k防止数组越界
f[x][k]=max(f[x][k],f[x][k-j]+f[r->data][j]);
r=r->next;//链表继续遍历
}
for(int i=s[x];i>=0;i--)
f[x][i+1]=f[x][i]+p[x];
```
为什么最后两行要单独拿出来做呢？
```
for(int i=s[x];i>=0;i--)
f[x][i+1]=f[x][i]+p[x];
```
我们回到题面上，父亲是儿子的先修课，所以没有父亲时，儿子再多也没有用，背包中处理的子树是不带根结点的，我们要加上，否则会出现下面这种状况：
如果在做的过程中将根结点算入子树，那么$\mathrm f[1][2]$最终值将会是$11$（在正确的过程中也是$11$，但是会被更新到$f[1][3]$），不做更新或再去做一遍更新就不对了，核心思想结束。
最后输出的是$f[0][m+1]$，所以$0$这个“根结点“”是非常方便的。
总结：
1. 树形DP要根据实际情况，改变循环顺序和方向；
1. 要判断根结点是否包含在子树，并在这个判断最终稍加处理
1. 状态要保存准确，不能丢失要用到的状态
------------
## Code:
```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[301],*tail[301];//用于链表
int f[301][301],s[301],n,m,p[301];
void dfs(int x)
{
node *root;
root=&head[x];
node *r=root->next;
while(root->next!=0)
{
root=root->next;
dfs(root->data);
s[x]+=s[root->data];
}
//开始背包
while(r!=0)
{
for(int k=s[x];k>=1;k--)
for(int j=1;j<=k;j++)//j是枚举r->data的选科个数
f[x][k]=max(f[x][k],f[x][k-j]+f[r->data][j]);
r=r->next;
}
for(int i=s[x];i>=0;i--)
f[x][i+1]=f[x][i]+p[x];
return ;
}
int main()
{
memset(s,0,sizeof(s));
memset(f,0,sizeof(f));
int a,b;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
tail[i]=&head[i];
for(int i=1;i<=n;i++)//建树存图
{
scanf("%d%d",&a,&b);
s[a]++;
node *t=new node();
t->data=i;
p[i]=b;
tail[a]->next=t;
tail[a]=t;
}
dfs(0);
printf("%d\n",f[0][m+1]);//m+1是因为把0当做一个结点（课程）
return 0;
}
```