题目链接：https://www.luogu.com.cn/problem/P1273

树形dp。但这个本质上是个背包问题，一时间没有想起来有依赖的背包问题。
读题的时候没有发现客户端一定是接在转发器上的，想成了一颗比较自由的树。

做的时候要当作一个有依赖的背包问题来做，分好组别，找出每个fij的最优值，直接倒序找>=0的那个下标

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 3010;
struct tdata{
	int num;
	int cost;
};
vector<tdata> ve[nn];
int n,m;
int w[nn];
int f[nn][nn];
//本质上是一个有依赖的背包问题，所求的是数量
//f[i][j] 表示i个节点选择j个用户所获得的的最大的价值，我们只需要保持这个价值不小于0就可以
//需要注意的地方是，客户端只能接在转播站上==这是读题的时候没有注意到的
//那么答案就是倒序找个>=0的值就可以了 
int dfs(int u){
	if(u>n-m){
		f[u][1] = w[u];
		return 1;
	}
	int sum = 0,t = 0;
	for(int i=0;i<ve[u].size();i++){
		int v = ve[u][i].num;
		int c = ve[u][i].cost;
		t = dfs(v);sum+=t;
		//分组背包的倒序 
		for(int j = sum;j>0;j--){
			for(int k=1;k<=t;k++)
				if(j-k>=0)
					f[u][j] = max(f[u][j],f[u][j-k]+f[v][k]-c); 
		}
	}
	return sum;
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
 	cin>>n>>m;
 	int k;
 	memset(f,~0x3f,sizeof f);
 	for(int i=1;i<=n-m;i++){
 		cin>>k;
 		int a,b;
 		for(int j=1;j<=k;j++){
 			cin>>a>>b;
			ve[i].push_back({a,b});	
		}
	}
	for(int i=n-m+1;i<=n;i++){
		cin>>w[i];
	}
	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){
			cout<<i<<endl;
			break;
		} 
	}
}