思路
请大家都去看王天懿的贪心问题选讲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;
}