选课

我觉得我好像已经理解树形背包了。

---

 套路化的树形背包。

递推公式长这样：f[i][j]=max(f[i][j],f[i][j-k]+f[t][k]);

注意f[i][0]应该在最后附为0，不然就相当于是取前m大了。

看代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
int n,m,f[maxn][maxn],val[maxn];
int beg[maxn<<1],nex[maxn<<1],to[maxn<<1],e;
inline void add(int x,int y){
    e++;nex[e]=beg[x];
    beg[x]=e;to[e]=y;
}
int sz[maxn];
inline void dfs(int x,int fa){
    f[x][1]=val[x];
    //f[x][0]=0;
    for(int i=beg[x];i;i=nex[i])
        if(to[i]!=fa)dfs(to[i],x);
    for(int i=beg[x];i;i=nex[i])
        if(to[i]!=fa)
        for(int j=m+1;j>=0;j--)
            for(int k=0;k<=j;k++)
        f[x][j]=max(f[x][j],f[x][j-k]+f[to[i]][k]);
    f[x][0]=0;
}
int main(){
    cin>>n>>m;
    int x,rt;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&val[i]);
        add(x,i);
    }
    memset(f,-0x3f,sizeof(f));
    dfs(0,0);
    printf("%d
",f[0][m+1]);
    return 0;
}

深深地感到自己的弱小。