输出格式

输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。

样例 #1

样例输入 #1

5 3
2 2 2 5 3
2 3 2 4 3
3 4 2

样例输出 #1

2

提示

样例解释

如图所示，共有五个结点。结点 ① 为根结点，即现场直播站，② 为一个中转站，③④⑤ 为用户端，共 (M) 个，编号从 (N-M+1) 到 (N)，他们为观看比赛分别准备的钱数为 (3)、(4)、(2)。

从结点 ① 可以传送信号到结点 ②，费用为 (2)；

也可以传送信号到结点 ⑤，费用为 (3)（第二行数据所示）；

从结点 ② 可以传输信号到结点 ③，费用为(2)；

也可传输信号到结点 ④，费用为 (3)（第三行数据所示）。

如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：(2+3+2+3=10)，大于用户愿意支付的总费用 (3+4+2=9)，有线电视网就亏本了，而只让 ③④ 两个用户看比赛就不亏本了。

解法

注意到本题的特征：从若干个物品中选出一些来满足某一个限制条件，符合背包问题的特征，因此我们可以从背包问题出发思考。
题目中要选择的目标是树的叶子节点，由于叶节点被子树分成了若干个组，因此这个问题就是一个分组背包问题：
分组背包问题模板(滚动数组优化版本)

for(int i = 1; i <= n; i ++ ){    //组数
        for(int j = V; j >= 0; j -- ){     //背包容量
            for(int k = 0; k <= sz[i]; k ++ ){          //枚举每一组中的物品
                int vik = v[i][k], wik = w[i][k];
                if(j >= vik) f[j] = std::max(f[j], f[j - vik] + wik);
            }
        }
    }

设(f[u][i][j])表示结点(u)的前(i)个儿子中选择(j)个结点的最大利润。我们考虑最后一个分界点：如果不取第(i)个结点，则状态转移为$$f[u][i][j] = f[u][i - 1][j]$$如果取第(i)个结点，记为(v)，那么状态转移方程为$$f[u][i][j] = f[u][i - 1][j - k] + f[v][sz[v]][k] - w_{u, v}$$其中(sz[v])表示(v)的子树大小，(k)表示从(v)的子树中选择的节点个数，(w_{u, v})是(u,v)之间的花费.所以最终的状态转移方程为$$f[u][i][j] = max_{v in son[u]}(f[u][i-1][j], f[u][i-1][j-k]+f[v][sz[v]][k] - w_{u,v})$$
显然根据(0/1)背包的思想我们可以对上式进行空间优化，只需要在枚举选择的节点个数时倒序枚举即可。优化后的状态转移方程为$$f[u][j] = max_{v in son[u]}(f[u][j], f[u][j - k] + f[v][k] - w_{u, v})$$
注意本题最终问的问题，是要在不亏本的情况下能够观看转播的最多用户数，也就是满足(f[1][j] geq 0)的最大的(j)，因此在做完后需要从大到小枚举(j)来找到答案。

#include<bits/stdc++.h>

const int N = 3010;
const int inf = 0xcfcfcfcf;

int n, m;

std::vector<std::vector<std::pair<int, int>>> g(N);
std::vector<std::vector<int>> f(N, std::vector<int>(N, inf));
int sz[N], money[N];

void dfs(int u) {
	if(money[u]) {
		f[u][1] = money[u];
		sz[u] = 1;
		return;
	}

	for(auto edge: g[u]) {
		int v = edge.first, w = edge.second;
		dfs(v);
		sz[u] += sz[v];
		for(int j = m; j >= 1; j -- ) {
			for(int k = 0; k <= std::min(j, sz[v]); k ++ ) {
				f[u][j] = std::max(f[u][j], f[u][j - k] + f[v][k] - w);
			}
		}
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	std::cin >> n >> m;

	for(int i = 1; i <= n - m; i ++ ) {
		int k;
		std::cin >> k;
		for(int j = 0; j < k; j ++ ) {
			int a, c;
			std::cin >> a >> c;
			g[i].push_back({a, c});
		}
	}

	for(int i = n - m + 1; i <= n; i ++ ) {
		std::cin >> money[i];
	}

	for(int i = 1; i <= n; i ++ ) f[i][0] = 0;

	dfs(1);
	int ans = 0;
	for(int i = m; i >= 1; i -- ) {
		if(f[1][i] >= 0) {
			ans = i;
			break;
		}
	}
	
	std::cout << ans;

	return 0;
}