题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n$、$k(1 \leq k \lt n \leq 10^5)$和一棵$n$个节点的无向树的$n-1$条边。节点编号从$1$开始。

你需要移除这棵树的恰好$k$条边。移除后，我们得到了$k+1$个连通块。

设$x$为最小连通块的大小（节点个数）。输出$x$的最大值。

输入样例

6
5 1
1 2
1 3
3 4
3 5
2 1
1 2
6 1
1 2
2 3
3 4
4 5
5 6
3 1
1 2
1 3
8 2
1 2
1 3
2 4
2 5
3 6
3 7
3 8
6 2
1 2
2 3
1 4
4 5
5 6

输出样例

2
1
3
1
1
2

算法

二分答案+树形DP

二分的思路比较容易想到，对于一个给定的连通块大小$blockSize$，如果所有划分出来的连通块大小都$\geq blockSize$，且删除的边数$\leq k$，那这个$blockSize$就有可能是答案，让$blockSize$更大肯定也能满足所有划分出来的连通块大小都不小于$blockSize$，且删除的边数不超过$k$。

这样就有了单调性，而我们的目的是希望找到一个最小的$blockSize$，且删除的边数不超过$k$。对于一个给定的$blockSize$，我们进行树形DP，求删除的边数：

1. 如果满足划分出来的连通块大小都$\geq blockSize$，且删除的边数$\leq k$，$blockSize$就有可能是答案，记录一下并往左搜索看能不能更小。
2. 否则$blockSize$就太小了，导致要删除的边太多，应该往右搜索增大这个块大小。

下面说明一下如何进行树形DP。

状态定义

$f[u][0]$表示以$u$为根的子树大小，$f[u][1]$表示以$u$为根的子树中，为了让所有划分出来的连通块大小$\geq blockSize$，一共删除了多少条边。

状态转移

转移方程比较简单，$f[u][0]=1+\Sigma_vf[v][0]$，$f[u][1]=\Sigma_vf[u][1]$，其中$v$为$u$的子节点。

1. 如果$f[u][0] \geq blockSize$，那$u$以下的连通块就要被划分出去，$f[u][1]$把$u$连向自己父亲节点的边删除，往其父节点返回$(0,f[u][1]+1)$。
2. 否则$u$上面的节点就要继续往已有的连通块中合并，不删边，往其父节点返回$(f[u][0],f[u][1])$。

复杂度分析

时间复杂度

在$[1,n]$上做二分答案，每次二分的$check$都是一次树形DP，时间复杂度为$O(n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

树的邻接表空间复杂度为$O(n)$，每次树形DP递归的最大深度也是$O(n)$级别。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int t, n, k;
vector<int> graph[N];

array<int, 2> dfs(int u, int fa, int bs) {
    int count = 1, delcnt = 0;
    for(int v: graph[u]) {
        if(v == fa) continue;
        auto pir = dfs(v, u, bs);
        count += pir[0], delcnt += pir[1];
    }
    if(count >= bs) return {0, delcnt + 1};
    return {count, delcnt};
}

bool check(int blockSize) {
    auto pir = dfs(1, 0, blockSize);
    return pir[1] <= k;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) {
            graph[i].clear();
        }
        for(int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        int l = 1, r = n;
        while(l < r) {
            int mid = l + r >> 1;
            if(check(mid)) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        printf("%d\n", r - 1);
    }
    return 0;
}