qkw 辅助数组版：

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int dp[N][N],n,m,dp1[N],siz[N],a[N];
vector<int>G[N];
void dfs(int x,int f)
{
	dp[x][0]=0;
	siz[x]=1;
	for(int y:G[x])if(y!=f)
	{
		dfs(y,x);
		memset(dp1,-0x3f,sizeof(dp1));
		for(int i=0;i<=min(siz[x],m);i++)
			for(int j=0;j<=min(siz[y],m-i);j++)
				dp1[i+j]=max(dp1[i+j],dp[x][i]+dp[y][j]);
		for(int i=0;i<=min(siz[x]+siz[y],m);i++)dp[x][i]=dp1[i];
		siz[x]+=siz[y];
	}
	if(x>n-m)dp[x][1]=a[x];
	else for(int i=siz[x];i>=1;i--)dp[x][i]=dp[x][i]+a[x];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n-m;i++)
	{
		int k;cin>>k;
		while(k--)
		{
			int x,y;cin>>x>>y;
			a[x]-=y;
			G[i].push_back(x);
		}
	}
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
		int x;cin>>x;
		a[n-m+i]+=x;
	}
	dfs(1,0);
	for(int i=m;i>=0;i--)if(dp[1][i]>=0){cout<<i;return 0;}
	return 0;
}

E78 树上背包 P1273 有线电视网

// 树上背包 O(n*m)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int read(){
  int x=0,f=1;char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
  return x*f;
}
const int N=3010;
int idx,head[N];
struct E{int to,w,ne;}e[N*N];
void add(int u,int v,int w){
  e[++idx]={v,w,head[u]};head[u]=idx;
}
int n,m;
int val[N],s[N],f[N][N];

void dfs(int u){
  if(u>n-m){f[u][1]=val[u]; s[u]=1; return;}
  for(int i=head[u];i;i=e[i].ne){
    int v=e[i].to;
    dfs(v);
    s[u]+=s[v];
    for(int j=s[u];j>=0;j--)
      for(int k=0;k<=min(j,s[v]);k++)
        f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-e[i].w);
  }
}
int main(){
  n=read(),m=read();
  for(int u=1;u<=n-m;u++){
    int k=read();
    for(int j=1;j<=k;j++){
      int v=read(),w=read();
      add(u,v,w);
    }
  }
  for(int i=n-m+1;i<=n;i++)val[i]=read();
  memset(f,~0x3f,sizeof(f));  
  for(int i=1;i<=n;i++) f[i][0]=0;
  dfs(1);
  for(int i=m;i>=0;i--)
    if(f[1][i]>=0){printf("%d",i); break;}
}

#include<bits/stdc++.h>
using namespace std;
struct trnode
{
	int lc, rc, lastc, c, num;
	trnode(){ lc=rc=lastc=num=0;}
}tr[3100];

int f[3100][3100];
void treedp(int x)
{
	if(x==0) return ;
	int lc=tr[x].lc, rc=tr[x].rc;
	if(lc==0 && rc==0) return ;
	treedp(lc);tr[x].num+=tr[lc].num;
	treedp(rc);tr[x].num+=tr[rc].num;
	for(int i=tr[x].num;i>=1;i--)
	{
		f[x][i]=max(f[x][i],f[rc][i]);
		if(lc==0 && rc!=0) f[x][i]=max(f[x][i],f[rc][i-1]+tr[x].c);
		if(lc!=0 && rc==0) f[x][i]=max(f[x][i],f[lc][i]  +tr[x].c);
		if(lc!=0 && rc!=0)
		{
			
			for(int ls=1;(ls<=tr[lc].num) && (ls<=i);ls++)
			{
				f[x][i]=max(f[x][i],f[lc][ls]+f[rc][i-ls]+tr[x].c);
			}
		}
    }
}
int main()
{
	int n, m;scanf("%d%d", &n, &m);
	for(int i=1;i<=n-m;i++)
    {
    	int k;scanf("%d", &k);
		for(int j=1;j<=k;j++)
		{
			int A, C;scanf("%d%d", &A, &C);
			tr[A].c=-C;
			if(tr[i].lastc==0) tr[i].lc=A;
			else  tr[ tr[i].lastc ].rc=A;
			tr[i].lastc=A;
        }
    }
    memset(f, -63, sizeof(f));
	for(int i=1;i<=n;i++)f[i][0]=0;
	
	for(int i=n-m+1;i<=n;i++)
	{
		int C;scanf("%d", &C);
		tr[i].c+=C;tr[i].num=1;f[i][1]=tr[i].c;
	}
    treedp(1);
    for(int i=n;i>=1;i--)if(f[1][i]>=0){printf("%d\n",i);break;}
    return 0;
}

#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n, m, W, d, siz[N], w[N], c[N];
vector<int>e[N];
int f[N][N];
void dfs(int x){
	if(x>n-m){
		siz[x]=1;
		f[x][1]=w[x];
	}
	for(int y:e[x]){
		dfs(y);siz[x]+=siz[y];
		for(int i=siz[x];i>=1;i--){
			for(int j=1;j<=min(i, siz[y]);j++){
				f[x][i]=max(f[x][i],f[x][i-j]+f[y][j]-c[y]);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n-m;i++){
		int k;cin>>k;
		for(int j=1;j<=k;j++){
			int y;cin>>y;cin>>c[y];c[y]=c[y];e[i].push_back(y);
		}
	}
	for(int i=n-m+1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=-1e9;
	dfs(1);
	for(int i=n;i>=1;i--)if(f[1][i]>=0){cout << i;return 0;}
	cout << 0;
}