思路：树上dp，每个点的权值为d[i]+G[i].size()，然后选择最小的删除就好
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 const int maxn = 2000000+10; 8 9 vector<int> G[maxn]; 10 int n,m,d[maxn],ans; 11 12 bool cmp(int x,int y){ 13 return d[x]<d[y]; 14 } 15 16 void dfs(int u){ 17 for(int i=0; i<G[u].size(); i++) 18 dfs(G[u][i]); 19 d[u] += G[u].size(); 20 sort(G[u].begin(),G[u].end(),cmp); // 贪心 从重量小的开始拿 21 for(int i=0; i<G[u].size(); i++){ 22 int v = G[u][i]; 23 if(d[u]+d[v]-1<=m){ 24 d[u] = d[u]+d[v]-1; 25 ans++; 26 } 27 else 28 break; 29 } 30 } 31 32 int main(){ 33 cin>>n>>m; 34 for(int i=0; i<n; i++) 35 scanf("%d",&d[i]); 36 for(int i=0; i<n; i++){ 37 int num; scanf("%d",&num); 38 for(int j=0; j<num; j++){ 39 int x; scanf("%d",&x); 40 G[i].push_back(x); 41 } 42 } 43 ans = 0; 44 dfs(0); 45 cout << ans << endl; 46 }