题目链接:https://codeforces.com/contest/1385/problem/F
题目大意:
给出一棵树,每次可以对一个顶点删除k个节点,问最多可以删除多少次
题目思路:
刚开始读错题了..以为每次可以删除k个叶子节点,想了好久
删除同一个节点的叶子节点就容易许多了
考虑一个节点成为叶子节点的条件:
首先需要度数为1,其次如果不是初始的叶子节点,那么他需要删除多余的叶子节点
用sz_i代表i节点删除了多少个子节点
当且仅当:
in[i] == 1 && sz[i]%m == 0
此时可以入队成为新的叶子节点
所以,整个过程嵌套一个拓扑排序就好了
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
const ll INF=1e17;
const int maxn =1e6+700;
const int mod= 1e9+7;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
int in[maxn];
vector<int>v[maxn];
int vis[maxn];
vector<int>g;
int sz[maxn];
void work(){
g.clear();
queue<int>q;
for(int i=1;i<=n;i++)
if(in[i]==1) q.push(i);
int ans = 0;
while(!q.empty()){
int u = q.front();q.pop();
vis[u] = 1;
for(int e:v[u]){
if(vis[e]) continue;///deleted
in[e]--;sz[e]++;
if(sz[e]%m == 0){
ans++;
if(in[e] == 1) q.push(e);
}
}
}
printf("%d\n",ans);
}
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);read(m);
for(int i=1;i<=n;i++) in[i] = 0,v[i].clear(),vis[i] = 0,sz[i] = 0;
for(int i=1;i<=n-1;i++){
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);in[y]++;
v[y].push_back(x);in[x]++;
}
work();
}
return 0;
}
/***
***/