← 返回题目列表

Codeforces · 1566/E

E. 芽重新悬挂

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

树是没有循环的连通图。有根树有一个特殊的顶点,称为根。顶点 $$$v$$$ 的父顶点(与根不同)是从根到顶点 $$$v$$$ 的最短路径上 $$$v$$$ 顶点的前一个顶点。顶点 $$$v$$$ 的子节点都是以 $$$v$$$ 为父节点的顶点。

如果一个顶点没有子节点,那么它就是一个叶子。如果满足以下三个条件,我们将顶点称为芽:

- 它不是根,
- 它至少有一个孩子,并且
- 它的所有子节点都是叶子。

给你一棵有 $$$n$$$ 个顶点的有根树。顶点 $$$1$$$ 是根。在一次操作中,您可以选择任何芽及其所有子代(它们是叶子)并将它们重新挂到树的任何其他顶点。通过执行此操作,您可以删除连接芽及其父级的边,并在芽和树的选定顶点之间添加一条边。所选顶点不能是芽本身或其任何子节点。芽的所有子代都与芽保持连接。

如果可以进行任意数量的上述操作(可能为零),则可以获得的最小叶子数量是多少?

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) - 给定树中的顶点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),这意味着树中的顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。

保证给定的图是一棵树。

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

输出

对于每个测试用例,打印一个整数 - 经过某些操作后可能获得的叶子的最小数量。

示例

输入 #1

5
7
1 2
1 3
1 4
2 5
2 6
4 7
6
1 2
1 3
2 4
2 5
3 6
2
1 2
7
7 3
1 5
1 3
4 6
4 7
2 1
6
2 1
2 3
4 5
3 4
3 6

输出 #1

2
2
1
2
1

注意

在第一个测试用例中,树如下所示:

首先你可以选择一个芽顶点$$$4$$$并将其重新挂到顶点$$$3$$$。之后,您可以选择一个芽顶点$$$2$$$并将其重新挂到顶点$$$7$$$。结果,您将得到以下带有 $$$2$$$ 叶子的树:

可以证明它是可能得到的最小叶子数。

在第二个测试用例中,树如下所示:

您可以选择一个芽顶点 $$$3$$$ 并将其重新挂到顶点 $$$5$$$。结果,您将得到以下带有 $$$2$$$ 叶子的树:

可以证明它是可能得到的最小叶子数。