← 返回题目列表

Codeforces · 1385/F

F. 去除叶子

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

给你一棵由 $$$n$$$ 个顶点组成的树(无环的连通图)。这棵树是无根的——它只是一个没有循环的连通无向图。

在一步操作中,您可以精确选择连接到同一顶点的 $$$k$$$ 叶子(叶子是一种仅与另一个顶点相连的顶点),并删除它们与它们相关的边。 IE。您选择这样的叶子 $$$u_1, u_2, \dots, u_k$$$ ,其中有边 $$$(u_1, v)$$$, $$$(u_2, v)$$$, $$$\dots$$$, $$$(u_k, v)$$$ 并删除这些叶子和这些边。

你的任务是找到在以最佳方式移除叶子的情况下可以执行的最大移动次数。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$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$$$),其中 $$$x_i$$$ 和 $$$y_i$$$ 是第 $$$i$$$ 条边连接的顶点。保证给定的边集形成一棵树。

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

输出

对于每个测试用例,打印答案 - 如果您以最佳方式移除叶子,则可以执行的最大移动次数。

示例

输入 #1

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

输出 #1

2
3
3
4

注意

示例第一个测试用例对应的图片:

您可以在第一次移动期间删除顶点 $$$2$$$、$$$5$$$ 和 $$$3$$$,在第二次移动期间删除顶点 $$$1$$$、$$$7$$$ 和 $$$4$$$。

示例的第二个测试用例对应的图片:

您可以在第一次移动期间删除顶点 $$$7$$$、$$$8$$$ 和 $$$9$$$,然后在第二次移动期间删除顶点 $$$5$$$、$$$6$$$ 和 $$$10$$$,在第三次移动期间删除顶点 $$$1$$$、$$$3$$$ 和 $$$4$$$。

示例的第三个测试用例对应的图片:

您可以在第一次移动期间删除顶点 $$$5$$$ 和 $$$7$$$,然后在第二次移动期间删除顶点 $$$2$$$ 和 $$$4$$$,在第三次移动期间删除顶点 $$$1$$$ 和 $$$6$$$。