由题：定义一个节点x对其父节点的贡献为 c[x] + son[x]
考虑贪心：从底向上贪心，每次将子节点按贡献从小到大的顺序删掉所有能删的
可以证明一定不会有更优的情况
首先显然对于一个节点的子节点肯定尽量选小的更优
所以只需要证明是否尽量把能选的选完就是最优的
假设不是，即如果选完了这个点的子节点后，这个点不能再被删
可以发现当这个点选的在多对于上一层只会影响一个答案，而这一层选了后对答案的影响一定不小于1
故贪心正确
#include<bits/stdc++.h> using namespace std; #define LL long long inline LL read() { LL f = 1,x = 0; char ch; do { ch = getchar(); if(ch == ‘-‘) f=-1; }while(ch<‘0‘||ch>‘9‘); do { x = (x<<3) + (x<<1) + ch - ‘0‘; ch = getchar(); }while(ch>=‘0‘&&ch<=‘9‘); return f*x; } const int MAXN = 2000000 + 10; int n,m; int c[MAXN]; vector<int>ve[MAXN]; int ans = 0; int son[MAXN]; inline bool cmp(int a,int b) { return c[a] + son[a] < c[b] + son[b]; } inline void dfs(int x) { for(int i=0;i<ve[x].size();i++) { int v = ve[x][i]; dfs(v); son[x] ++; } sort(ve[x].begin(),ve[x].end(),cmp); for(int i=0;i<ve[x].size();i++) { int v = ve[x][i]; if(c[x]+son[x]+c[v]+son[v]-1<=m) { ans++; c[x]+=c[v]; son[x]+=son[v]-1; } else break; } } int main() { n = read(),m = read(); for(int i=1;i<=n;i++) c[i] = read(); for(int i=1;i<=n;i++) { int k = read(); for(int j=1;j<=k;j++) { int x = read() + 1; ve[i].push_back(x); } } dfs(1); cout<<ans<<endl; }
原文：https://www.cnblogs.com/wlzs1432/p/11723543.html