C. Tree Cutting
You are given a tree with $n$ vertices.
Your task is to find the maximum number $x$ such that it is possible to remove exactly $k$ edges from this tree in such a way that the size of each remaining connected component$^†$ is at least $x$.
$^†$ Two vertices $v$ and $u$ are in the same connected component if there exists a sequence of numbers $t_1,t_2,…,t_k$ of arbitrary length $k$, such that $t_1=v$, $t_k=u$, and for each $i$ from $1$ to $k−1$, vertices $t_i$ and $t_i+1$ are connected by an edge.
Input
Each test consists of several sets of input data. The first line contains a single integer $t (1≤t≤10^4)$ — the number of sets of input data. This is followed by a description of the sets of input data.
The first line of each set of input data contains two integers $n$ and $k (1≤k<n≤10^5)$ — the number of vertices in the tree and the number of edges to be removed.
Each of the next $n−1$ lines of each set of input data contains two integers $v$ and $u (1≤v,u≤n)$ — the next edge of the tree.
It is guaranteed that the sum of the values of $n$ for all sets of input data does not exceed $10^5$.
Output
For each set of input data, output a single line containing the maximum number $x$ such that it is possible to remove exactly $k$ edges from the tree in such a way that the size of each remaining connected component is at least $x$.
example
input
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
output
2
1
3
1
1
2
差不多是正经C题的难度
题意解读
题意:给定一棵 $n$ 个结点的树,问去除 $k$ 条边后,剩余部分最小的剩余节点构成“团”的最大内含结点数量是多少
思路
之前没做出来还是因为思路想偏了,但其实这题思路不难
题意还是比较清楚的,由于求答案 最大的最小值, 所以应该第一时间先想到 二分
直接枚举答案 $size$, 求出在每种 $size$ 下能分成多少块,分割方法采用 dfs + 贪心
细节上需要注意:
1. 这题中的树默认是无向边,我一开始写成有向边导致WR
2. 二分的判断条件,看清楚题目中 $k$ 是指边数量,所以至少划分成 $k + 1$块才满足条件
3. 被切断的树直接 $size$ 置为 $0$ 即可
4. 常见写法防止回边
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200010;
int h[N], e[N], ne[N], idx;
int t, n, m, cnt;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int x, int f, int mid)
{
int res = 1;
for(int i = h[x]; ~i; i = ne[i])
{
int j = e[i];
if(j == f) continue;
res += dfs(j, x, mid);
}
if(res >= mid){
cnt ++;
return 0;
}
return res;
}
bool check(int mid)
{
cnt = 0;
dfs(1, -1, mid);
if(cnt >= m + 1) return true;
return false;
}
int main()
{
cin >> t;
while(t --)
{
memset(h, -1, sizeof h);
idx = 0;
cin >> n >> m;
for(int i = 1; i < n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
int l = 1, r = n;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(!check(mid)) r = mid - 1;
else l = mid;
}
cout << l << endl;
}
return 0;
}
%%% 感谢题解