P2014 选课
斯德哥尔摩
2018-11-05 09:19:15
[P2014 选课](https://www.luogu.org/problemnew/show/P2014)
一眼看去——树形背包。
设$dp[i][j]$表示在以$i$为根的子树中，必须选$i$，并且选了$j$个点的最大权值。
有经验的估计转移方程立马就想好了：
$$dp[i][j]=\max\{\ dp[i][j-k]+dp[v][k]\ |\ v\in son_i,k\in[0,j)\ \}$$
但是多颗子树怎么办？
没事，我们新设立一个树根$rt$，把所有的原来的树根连到$rt$的字树上。
然后从$rt$开始跑树形$DP$即可。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 310
using namespace std;
int n,m,root,c=1;
int head[MAXN],val[MAXN],deep[MAXN],size[MAXN],dp[MAXN][MAXN];
struct Tree{
int next,to;
}a[MAXN<<1];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void add(int x,int y){
a[c].to=y;a[c].next=head[x];head[x]=c++;
a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs(int rt){
size[rt]=1;
dp[rt][0]=0;dp[rt][1]=val[rt];
int will;
for(int i=head[rt];i;i=a[i].next){
will=a[i].to;
if(!deep[will]){
deep[will]=deep[rt]+1;
dfs(will);
size[rt]+=size[will];
for(int j=m+1;j>=1;j--){
for(int k=1;k<=size[will]&&k<j;k++){
dp[rt][j]=max(dp[rt][j],dp[rt][j-k]+dp[will][k]);
}
}
}
}
}
void work(){
int x;
n=read();m=read();
root=n+1;
for(int i=1;i<=n;i++){
x=read();val[i]=read();
if(x)add(i,x);
else add(root,i);
}
val[root]=0;
deep[root]=1;
dfs(root);
printf("%d\n",dp[root][m+1]);
}
int main(){
work();
return 0;
}
```