一道水紫
考虑贪心
我们把一个点所有儿子删除所需呀给这个点加的代价排序。
然后贪心地删除。
核心代码
void dfs(int x,int fa)
{
int son=0;
vector<int>b;
for(auto i:v[x])
{
if(i==fa) continue;
son++;
b.push_back(i);
dfs(i,x);
}
val[x]=a[x]+son;
sort(b.begin(),b.end(),cmp);
for(int i=0;i<son;++i)
if(val[x]+val[b[i]]-1<=m) ans++,val[x]+=val[b[i]]-1;
}