https://www.luogu.org/problemnew/show/P1273

C++版本一

树状DP

我们设dp[i][j]表示在以i为根的子树中，满足j个客户的需求所能获得的最大收益，

那么在最终求最多客户时，只要求最大的dp[1][i]>=0的i就行了。

至于分组背包，我们设dp[i][u][j]表示以u为根的子树，仅用前i个儿子，满足j个客户取得最大价值，

那么dp[i][u][j]=max(dp[i-1][u][j-k]+dp[full_son_size[v]][v][k]);

而i这一维可以直接用滚动数组优化掉。

而这个背包，有些细节优化是可以过掉讨论中的那个极限数据。

如，将下面题解代码中sum+=x改到dp后。然后把dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k])

改为dp[u][j+k]=max(dp[u][j+k],dp[u][j]+dp[v][k])，最后把dp[u][j]先用一个数组t保存一下就行了。

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=3000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp,a,c;
int v[N];
char str;
vector<int>G[N];
int w[N];
int dp[N][N];
int dfs(int rt){
    dp[rt][0]=0;
    if(rt>n-m){
        dp[rt][1]=v[rt];
        return 1;
    }
    int res=0;
    for(int i=0,j=G[rt].size();i<j;i++){
        int u=rt;
        int v=G[rt][i];
        int tmp=dfs(v);
        res+=tmp;
        for(int k=res;k>0;k--){
            int minl=min(tmp,k);
            for(int l=1;l<=minl;l++){
                dp[u][k]=max(dp[u][k],dp[u][k-l]+dp[v][l]-w[v]);
            }
        }
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
    //scanf("%d",&t);
    //while(t--){}
    for(int i=1;i<=n-m;i++){
        scanf("%d",&k);
        for(int j=1;j<=k;j++){
            scanf("%d%d",&a,&c);
            G[i].push_back(a);
            w[a]=c;
        }
    }
    for(int i=n-m+1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    memset(dp,~0x3f,sizeof(dp));
    dfs(1);
    for(int i=m;i>=0;i--){
        if(dp[1][i]>=0){
            cout<<i<<endl;
            break;
        }
    }
    //cout << "Hello world!" << endl;
    return 0;
}