解题思路
简单贪心,优先选择叶子节点最多的,这样能够保证一定能把所有能删的都删了。
因为要建一个可删除的图,所以我们可以使用 set 来存边,不然就需要维护一堆东西……那么我们肯定是从有叶子节点的点向父亲更新的,那么我们每次选择叶子节点最多的点,然后删除 \(k\) 个叶子,判断一下删除后该节点是否为叶子节点,如果是,那么更新父亲节点的叶子节点数量,否则把这个节点从新插入 set 中。
AC 代码
#include<stdio.h>
#include<stdlib.h>
#include<set>
#include <vector>
#define N 200005
int n,k,in[N],son[N];
std::set<int> edge[N];
struct cmp{
inline bool operator()(
const int a,
const int b
) const {
if(son[a]!=son[b])
return son[a]>son[b];
return a<b;
}
};
inline void work(){
scanf("%d%d",&n,&k);int u,v;
for(register int i=1;i<=n;++i)
edge[i].clear(),son[i]=in[i]=0;
for(register int i=1;i<n;++i){
scanf("%d%d",&u,&v);
edge[u].insert(v);
edge[v].insert(u);
++in[u],++in[v];
}std::set<int,cmp> s;
for(register int i=1;i<=n;++i){
if(in[i]>1) continue;
auto v=*edge[i].begin();
edge[i].erase(v);
edge[v].erase(i);
++son[v];
}int ans=0;
for(register int i=1;i<=n;++i)
s.insert(i);
while(!s.empty()){
auto now=*s.begin();
if(son[now]<k) break;
++ans;s.erase(now);
son[now]-=k;
if(!son[now]&&edge[now].size()==1){
if(edge[now].empty())
continue;
auto v=*edge[now].begin();
edge[now].erase(v);
edge[v].erase(now);
s.erase(v);++son[v];
s.insert(v);
}else s.insert(now);
}printf("%d\n",ans);
}
signed main(){
int T;scanf("%d",&T);
while(T--) work();
}
标签:int,题解,Leaves,son,叶子,edge,Removing,include,节点
From: https://www.cnblogs.com/UncleSamDied6/p/18010663