10分求助
查看原帖
10分求助
375242
ynxynx楼主2022/3/6 14:58
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001],val[3001][3001],vall[3001],dp[100001],f[10001];
vector <int> v[3001];
void dfs(int now){
	for (int i=0;i<v[now].size();i++) {
		int y=v[now][i];
		dfs(y);
		if (y<=n-m) {
			if (dp[y]>=val[now][y]) dp[now]=dp[now]+dp[y]-val[now][y],f[now]+=f[y];
		}
		else {
			if (vall[y]>=val[now][y]) dp[now]=dp[now]+vall[y]-val[now][y],f[now]++;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1;i<=n-m;i++) {
		cin>>a[i];
		for (int j=1;j<=a[i];j++) {
			int u,id;
			cin>>id>>u;
			v[i].push_back(id);
			val[i][id]=u;
		}
	}
	for (int i=n-m+1;i<=n;i++) cin>>vall[i];
	dfs(1);
	cout<<f[1];
}

10分

2022/3/6 14:58
加载中...