记录编号	610260	评测结果	AAAAAAAAAA
题目名称	有线电视网	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2025-12-18 23:06:10	内存使用	38.22 MiB

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 3005;
int n, m;
struct node{
	int u, w;
};
vector<node> e[MAXN];
int a[MAXN], sz[MAXN];
int f[MAXN][MAXN];

void dfs(int u){
	f[u][0] = 0;
	if(e[u].empty()){
		f[u][1] = a[u];
		return;
	}
	for(int i = 0;i < e[u].size();i ++){
		int v = e[u][i].u, w = e[u][i].w;
		dfs(v);
		for(int j = min(m, sz[u]);j >= 1;j --){
			for(int k = max(0, j - sz[u] - sz[v]);k <= min(j, sz[v]);k ++){
				f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] - w);
			}
		}
	}
}

void dfs2(int u){
	sz[u] = 1;
	for(int i = 0;i < e[u].size();i ++){
		int v = e[u][i].u;
		dfs2(v);
		sz[u] += sz[v];
	}
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(f, -0x3f3f3f3f, sizeof(f));
    cin >> n >> m;
    for(int i = 1;i <= n - m;i ++){
    	int k; cin >> k;
    	for(int j = 1;j <= k;j ++){
    		int c, w; cin >> c >> w;
    		e[i].push_back({c, w});
		}
	}
	for(int i = n - m + 1;i <= n;i ++){
		cin >> a[i];
	}
	dfs2(1);
	dfs(1);
    int ans = 0;
    for(int i = m;i >= 0;i --){
        if(f[1][i] >= 0){
            ans = i;
            break;
        }
    }
	cout << ans << '\n';
    return 0;
}