BZOJ 4027: [HEOI2015]兔子与樱花 树上dp

点击打开链接

思路：树上dp，每个点的权值为d[i]+G[i].size()，然后选择最小的删除就好

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int maxn = 2000000+10;vector<int> G[maxn];int n,m,d[maxn],ans;bool cmp(int x,int y){	return d[x]<d[y];}void dfs(int u){	for(int i=0; i<G[u].size(); i++)		dfs(G[u][i]);	d[u] += G[u].size();	sort(G[u].begin(),G[u].end(),cmp); // 贪心 从重量小的开始拿	for(int i=0; i<G[u].size(); i++){		int v = G[u][i];		if(d[u]+d[v]-1<=m){			d[u] = d[u]+d[v]-1;			ans++;		}		else			break;	}}int main(){	cin>>n>>m;	for(int i=0; i<n; i++)		scanf("%d",&d[i]);	for(int i=0; i<n; i++){		int num; scanf("%d",&num);		for(int j=0; j<num; j++){			int x; scanf("%d",&x);			G[i].push_back(x);		}	}	ans = 0;	dfs(0);	cout << ans << endl;}