← 返回题目列表

Codeforces · 2018/C

C. 树木修剪

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

给你一棵有 $$$n$$$ 个节点的树,根节点为 $$$1$$$。在这个问题中,叶子是度为 $$$1$$$ 的非根节点。

在一次操作中,您可以移除一片叶子及其相邻的边缘(可能会出现新叶子)。要获得一棵树(同样以节点 $$$1$$$ 为根,且所有叶子与根的距离相同),至少需要执行多少次操作?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 5 \cdot 10^5$$$) — 节点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$、$$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$),描述连接 $$$u$$$ 和 $$$v$$$ 的边。保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数:实现目标所需的最少操作数。

示例

输入 #1

3
7
1 2
1 3
2 4
2 5
4 6
4 7
7
1 2
1 3
1 4
2 5
3 6
5 7
15
12 9
1 6
6 14
9 11
8 7
3 5
13 5
6 10
13 15
13 6
14 12
7 2
8 1
1 4

输出 #1

2
2
5

注意

在前两个示例中,树如下:

在第一个示例中,通过删除边 $$$(1, 3)$$$ 和 $$$(2, 5)$$$,生成的树的所有叶子(节点 $$$6$$$ 和 $$$7$$$)与根(节点 $$$1$$$)的距离相同,即 $$$3$$$。答案是 $$$2$$$,因为它是实现目标需要删除的最小边数。

在第二个示例中,删除边 $$$(1, 4)$$$ 和 $$$(5, 7)$$$ 会生成一棵树,其中所有叶子(节点 $$$4$$$ 和 $$$5$$$)与根(节点 $$$1$$$)的距离相同,即 $$$2$$$。