F. Removing Leaves
题意有一棵树，共有n个节点 n-1条边
每次从同一个节点上去除k个叶子，问最多去除几次。
题解
贪心的策略是：每次剪掉即可。因为剪去叶子不会对其他的节点产生负影响。也就是
说，剪除一次以后，只会说多出一个节点可以减，不会说剪除了以后导致其他节点减不
了。因此这道题根本不用考虑剪枝的先后问题，直接剪就行了。
具体实现
考虑类比拓扑排序，将叶子结点入队，然后对其相邻结点遍历，当被遍历次数到达k
次，ans++，如果此时度数为1就入队，注意需要用vis数组标记一下那些结点已经入过
队，且标记时需要在queue，一次标记一个，因为存在edge(u,v)，这样的情况，度数都
是1，但是如果都标记了，就算不了贡献了
参考博客 参考博客
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e5+5;
vector<int>mp[Max];
int edge[Max],viscnt[Max];
bool vis[Max];
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)edge[i]=0,mp[i].clear();
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
mp[u].push_back(v);
mp[v].push_back(u);
edge[u]++;edge[v]++;
}
if(k==1)cout<<n-1<<endl;
else{
queue<int>leave;int ans=0;
for(int i=1;i<=n;i++){
if(edge[i]==1)leave.push(i);
vis[i]=0,viscnt[i]=0;
}
while(!leave.empty()){
int u=leave.front();
leave.pop();vis[u]=1;
for(auto i:mp[u]){
if(vis[i])continue;
viscnt[i]++;edge[i]--;
if(viscnt[i]%k==0){
ans++;
if(edge[i]==1)leave.push(i);
}
}
}
cout<<ans<<endl;
}
}
}
|