【模板】树形背包及泛化物品优化

#include<bits/stdc++.h>
using namespace std;
int k[310],w[310],c[310];
vector<int>g[310];
int n,m;
int dp[310][310];
//基本树形背包-O(n*C^2) 
void bag_tree(int x,int pre)
{
    int to;
    dp[x][c[x]]=w[x];
    for(int i=0;i<g[x].size();i++)
    {
        to=g[x][i];
        if(to==pre)continue;
        bag_tree(to,x);
        for(int j=m;j>=c[x];j--)
            for(int k=j-c[x];k>=c[to];k--)
                dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[to][k]);
    }
    return;
}
//树形背包-泛化物品优化-O(N*C) 
void bag_fastree(int x,int pre,int C)
{
    if(C<0)return;
    int to;
    for(int i=0;i<g[x].size();i++)
    {
        to=g[x][i];
        if(to==pre)continue;
        for(int j=0;j<=C-c[to];j++)dp[to][j]=dp[x][j]+w[to];
        bag_fastree(to,x,C-c[to]);
        for(int j=c[to];j<=C;j++)dp[x][j]=max(dp[x][j],dp[to][j-c[to]]);
    }
    return;
}
int main()
{
    memset(w,0,sizeof w);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>k[i]>>w[i];
        g[k[i]].push_back(i);
    }
    memset(dp,0,sizeof dp);
    fill(c+1,c+n+1,1);
    bag_fastree(0,-1,m);
    cout<<dp[0][m]<<endl;
    return 0;
}