CF1946C.Tree Cutting

给定一棵有 $n$ 个顶点的树。

你的任务是找到最大的整数 $x$，使得可以恰好从这棵树中删除 $k$ 条边，使得每个剩余连通分量的大小都至少为 $x$。

两个顶点 $v$ 和 $u$ 在同一个连通分量中，当且仅当存在一个长度为 $k$ 的数列 $t_1, t_2, \ldots, t_k$，满足 $t_1 = v$，$t_k = u$，并且对于每个 $i$ 从 $1$ 到 $k-1$，顶点 $t_i$ 和 $t_{i+1}$ 之间有一条边。

输入包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示数据组数。接下来是每组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $k$（$1 \le k < n \le 10^5$），分别表示树的顶点数和要删除的边数。

接下来的 $n-1$ 行中，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$），表示树中的一条边。

保证所有数据组中 $n$ 的总和不超过 $10^5$。

对于每组输入数据，输出一行一个整数，表示可以删除恰好 $k$ 条边后，每个剩余连通分量的最小大小的最大值 $x$。

第一组输入数据对应的树如下：

删除边 $1$ — $3$ 后，树变为：

此时树被分成两个连通分量。第一个分量包含顶点 $1$ 和 $2$，第二个分量包含顶点 $3, 4, 5$。两个连通分量的大小都至少为 $2$。可以证明答案 $3$ 不可实现，所以答案为 $2$。

由 ChatGPT 4.1 翻译