← 返回题目列表

Codeforces · 1905/B

B. 初学者的塞尔达

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

你有一棵树$$$^{\dagger}$$$。在一项塞尔达操作中,您可以执行以下操作:

- 选择树 $$$u$$$ 和 $$$v$$$ 的两个顶点;
- 将 $$$u$$$ 到 $$$v$$$ 路径上的所有顶点压缩为一个顶点。换句话说,从$$$u$$$到$$$v$$$路径上的所有顶点都将从树中删除,并创建一个新的顶点$$$w$$$。然后,从 $$$u$$$ 到 $$$v$$$ 的路径上与某个顶点有边的每个顶点 $$$s$$$ 都将有与顶点 $$$w$$$ 的边。

对顶点 $$$1$$$ 和 $$$5$$$ 执行的 zelda 操作的图示。

确定树只有一个顶点所需的最小塞尔达操作数。

$$$^{\dagger}$$$树是连通的非循环无向图。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 顶点数。

接下来的 $$$n − 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — 由第 $$$i$$$ 条边连接的顶点数。

保证给定的边形成一棵树。

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

输出

对于每个测试用例,输出一个整数——树只有一个顶点所需的最小塞尔达操作数。

示例

输入 #1

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

输出 #1

1
3
2
2

注意

在第一个测试用例中,对顶点 $$$2$$$ 和 $$$4$$$ 执行一次塞尔达操作就足够了。

在第二个测试用例中,我们可以执行以下 zelda 操作:

1. $$$u = 2,v = 1$$$。将添加的顶点标记为 $$$w = 10$$$;
2. $$$u = 4,v = 9$$$。将添加的顶点标记为 $$$w = 11$$$;
3. $$$u = 8,v = 10$$$。执行此操作后,树将由单个顶点组成。