CF1385F. Removing Leaves（贪心）

题意：

给出一棵树，每次可以剪掉同一顶点的k个叶子，询问最多能剪几次。

题解：

如果k是1，那么答案就是n-1。

然后开一个队列，每次把叶子数大于k的叶子入队，取出队头的时候更新叶子数。全学jiangly的。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
vector<int> g[maxn];
int lf[maxn];
int wjm[maxn];
int t,n,k;
int main () {
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&k);
        for (int i=1;i<=n;i++) g[i].clear(),lf[i]=0,wjm[i]=0;
        for (int i=1;i<n;i++) {
            int x,y;
            scanf("%d%d",&x,&y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        if (k==1) {
            printf("%d
",n-1);
            continue;
        }
        int ans=0;
        
        for (int i=1;i<=n;i++) {
            wjm[i]=g[i].size();
            if (wjm[i]==1) lf[g[i][0]]++;
        }
        int inq[n+1]={0};
        queue<int> q;
        for (int i=1;i<=n;i++) {
            if (lf[i]>=k) {
                q.push(i);
                inq[i]=1;
            }
        }
        while (!q.empty()) {
            int u=q.front();
            q.pop();
            ans++;
            lf[u]-=k;
            wjm[u]-=k;
            inq[u]=0;
            if (lf[u]>=k) {
                q.push(u);
                inq[u]=1;
            }
            if (wjm[u]==1) {
                wjm[u]=0;
                for (auto v:g[u]) {
                    if (wjm[v]) {
                        lf[v]++;
                        if (lf[v]>=k&&!inq[v]) {
                            q.push(v);
                            inq[v]=1; 
                        }
                    }
                }
            }
        }
        printf("%d
",ans);
    }
}