CF1385F Removing Leaves 题解

题意：

给定一棵树（无环的连通图），由 \(n\) 个顶点组成。这棵树是无根树——它只是一个没有环的连通无向图。

在一次移动中，你可以选择恰好 \(k\) 个叶子（叶子是指连接到仅一个其他顶点的顶点）与同一个顶点相连，并移除它们及与它们相连的边。也就是说，你选择这样的叶子 \(u_1, u_2, \dots, u_k\)，使得存在边 \((u_1, v)\)，\((u_2, v)\)，\(\dots\)，\((u_k, v)\)，然后移除这些叶子及这些边。

你的任务是找出如果你以最优方式移除叶子，你可以执行的最大移动次数。

你需要回答 \(t\) 个独立的测试用例。

省流：

给定一棵树，定义一次操作为"删除拥有同样父亲的 \(k\) 个叶节点"。请问最多能够进行多少次操作。

输入格式：

输入的第一行包含一个整数 \(t\) (\(1 \le t \le 2 \cdot 10^4\)) — 测试用例的数量。然后是 \(t\) 个测试用例。

每个测试用例的第一行包含两个整数 \(n\) 和 \(k\) (\(2 \le n \le 2 \cdot 10^5\); \(1 \le k < n\)) — 树中顶点的数量以及一次移除中你要移除的叶子的数量。接下来的 \(n-1\) 行描述边。第 \(i\) 条边由两个整数 \(x_i\) 和 \(y_i\) (\(1 \le x_i, y_i \le n\)) 表示，表示第 \(i\) 条边连接的两个顶点。保证给定的边构成一棵树。

保证 \(n\) 的总和不超过 \(2 \cdot 10^5\) (\(\sum n \le 2 \cdot 10^5\))。

输出格式：

对于每个测试用例，输出一个答案——如果你以最优方式移除叶子，你可以执行的最大移动次数。

这道题思维难度不高，代码实现的细节比较多。

考虑直接用队列维护所有「子节点（同时是叶节点）数量大于等于 \(k\) 」的节点。

每考虑一个新的节点，就删除 \(k\) 的倍数个它的儿子。当这个节点满足上述条件时把它放到队列里。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

queue<int> q;
struct Edge{ int v, next; } e[N * 2];
int n, pos = 1, head[N], sz[N], in[N];
void addEdge(int u, int v) { e[++pos] = {v, head[u]}; head[u] = pos; ++in[v]; }
void clear()
{
    for(int i = 1; i <= pos; i++) e[i] = {0, 0};
    pos = 1;
    for(int i = 1; i <= n; i++) { sz[i] = in[i] = head[i] = 0; }
}
void solve()
{
    int k; clear(); cin >> n >> k; 
    for(int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        addEdge(u, v); addEdge(v, u);
    }
    if(n == 2) { cout << "1\n"; return ; }
    int cnt = n, res = 0;
    for(int i = 1; i <= n; i++) if(in[i] == 1) ++sz[e[head[i]].v];
    while(true)
    {
        while(!q.empty()) q.pop();
        for(int i = 1; i <= n; i++) if(sz[i] >= k) q.push(i);
        if(q.empty()) break;
        while(!q.empty())
        {
            int u = q.front(); q.pop();
            if(sz[u] < k || cnt <= k) break;
            int t = sz[u] / k * k;
            sz[u] -= t; in[u] -= t; cnt -= t; res += t / k;
            for(int i = head[u], lst = 0; i; i = e[i].next)
            {
                int v = e[i].v;
                if(in[v] == 1)
                {
                    in[v] = head[v] = 0;
                    if(lst) e[lst].next = e[i].next; else head[u] = e[i].next;
                }else lst = i;
            }
            if(in[u] != 1) continue;
            ++sz[e[head[u]].v];
            if(sz[e[head[u]].v] >= k) q.push(e[head[u]].v);
        }
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}