一个树形背包问题,$f_{x,i}=\min\{f[y][j]+f[x][i-j]\}$
选自己的时候也要更新一下答案。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=305;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N][N],h[N],c[N],n,m;
struct edge{int y,next;}a[N];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void treedp(int x)
{
    c[x]=1;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;treedp(y);
        c[x]+=c[y];int mn=min(c[x],m);
        for(int i=mn;i>=0;i--)//倒序01背包 
        {
            int mnn=min(i,c[y]);
            for(int j=mnn;j>=0;j--)
                f[x][i]=max(f[x][i],f[x][i-j]+f[y][j]);
        }
    }
    if(x)for(int i=m;i>=1;i--)f[x][i]=f[x][i-1]+h[x];
}
int main()
{
    qr(n),qr(m);
    for(int i=1,x;i<=n;i++)qr(x),qr(h[i]),ins(x,i);
    treedp(0);
    qw(f[0][m]);puts("");
    return 0;
}