Miku

从叶子结点开始，自下而上得跑分组背包

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int s[301];
struct b{
    int to;
    int ne;
}e[301];
int son[301];
int p;
int dp[301][301];
int so[301][301];
int cnt[301];
int head[301];
void add(int f,int to){
    p++;
    e[p].ne=head[f];
    e[p].to=to;
    head[f]=p;
}
int x,y;
void dpp(int now){
    son[now]=1;
    for(int i=head[now];i;i=e[i].ne){
        cnt[now]++;
        so[now][cnt[now]]=e[i].to;
        dpp(e[i].to);
        son[now]+=son[e[i].to];
    }
        dp[now][1]=s[now];
    for(int i=1;i<=cnt[now];++i){
        for(int j=m+1;j;--j){//因为有0点并且必选        
            for(int k=0;k<j;++k){
                    dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[so[now][i]][k]);
            }
        }
    }

}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&y);
        add(x,i);
        s[i]=y;
    }
    dpp(0);
    cout<<dp[0][m+1];//多出来的时不存在的0 
    return 0;
}