题解 | #[HEOI2015]兔子与樱花#

思路

请大家都去看王天懿的贪心问题选讲ppt

代码

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e6+7;
const int mod=1e9+7;

int n,m,ans=0,val[N],a[N];
vector<int>G[N];

void dfs(int x){
	for(auto to:G[x]) dfs(to);
	int tot=0;
	for(auto to:G[x]) a[++tot]=val[to];
	sort(a+1,a+1+tot);
	for(int i=1;i<=tot;i++){
		if(val[x]+a[i]-1<=m){
			val[x]+=a[i]-1;
			ans++;
		}else break;
	}
}

void Solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>val[i];
	for(int i=1,k;i<=n;i++){
		cin>>k;
		val[i]=val[i]+k;
		for(int j=1,v;j<=k;j++){
			cin>>v;
			v++;
			G[i].push_back(v);
		}
	}
	dfs(1);
	cout<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
	//cin>>T;
	while(T--){
		Solve();
	}
//	cerr<<clock()*1.0/CLOCKS_PER_SEC<<endl;
	return 0;
}