← 返回题目列表

Codeforces · 1946/C

C. 砍树

中文机器翻译题面 查看原题

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

你的任务是找到最大数量$$$x$$$,这样就可以从这棵树中精确删除$$$k$$$边,使得每个剩余连接组件$$$^{\dagger}$$$的大小至少为$$$x$$$。

$$$^{\dagger}$$$ 如果存在任意长度 $$$k$$$ 的数字序列 $$$t_1, t_2, \ldots, t_k$$$,则两个顶点 $$$v$$$ 和 $$$u$$$ 位于同一连通分量中,使得 $$$t_1 = v$$$, $$$t_k = u$$$,对于从 $$$1$$$ 到 $$$k - 1$$$ 的每个 $$$i$$$,顶点 $$$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$$$。

输出

对于每组输入数据,输出包含最大数量 $$$x$$$ 的单行,以便可以从树中精确删除 $$$k$$$ 边,使得每个剩余连接组件的大小至少为 $$$x$$$。

示例

输入 #1

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

输出 #1

2
1
3
1
1
2

注意

第一组输入数据中的树:

删除边 $$$1$$$ — $$$3$$$ 后,树将如下所示:

树已分裂为两个连接的组件。第一个组件由两个顶点组成:$$$1$$$ 和 $$$2$$$。第二个连通分量由三个顶点组成:$$$3、4$$$ 和 $$$5$$$。在两个连通分量中,至少有两个顶点。可以看出,答案$$$3$$$是无法实现的,所以答案是$$$2$$$。