← 返回题目列表

Codeforces · 1689/C

C. 受感染的树

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

Byteland 是一片美丽的土地,因其美丽的树木而闻名。

Misha 找到了一棵有 $$$n$$$ 个顶点的二叉树,编号从 $$$1$$$ 到 $$$n$$$。二叉树是一个非循环连接的双向图,包含 $$$n$$$ 个顶点和 $$$n - 1$$$ 个边。每个顶点的度数最多为 $$$3$$$,而根是数字为 $$$1$$$ 的顶点,其度数最多为 $$$2$$$。

不幸的是,根被感染了。

以下过程发生 $$$n$$$ 次:

- Misha 要么选择一个未受感染(且未删除)的顶点,并将其连同所有在此顶点结束的边一起删除,要么什么都不做。
- 然后,感染传播到通过边连接到已感染顶点的每个顶点(所有已感染顶点仍处于感染状态)。

由于 Misha 没有太多时间思考,请告诉他最多可以保存多少个免受感染的顶点(注意,删除的顶点不计入保存)。

输入

输入数据中有多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 5000$$$) — 测试用例的数量。接下来是测试用例描述。

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

测试用例中以下 $$$n-1$$$ 行中的第 $$$i$$$ 行包含两个正整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),这意味着图中它们之间存在边。

保证该图是一个以 $$$1$$$ 为根的二叉树。还保证所有测试用例的 $$$n$$$ 总和不会超过 $$$3\cdot 10^5$$$。

输出

对于每个测试用例,输出 Misha 可以保存的最大顶点数。

示例

输入 #1

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

输出 #1

0
2
2
10

注意

在第一个测试用例中,唯一可能的操作是删除顶点 $$$2$$$,之后我们总共保存 $$$0$$$ 个顶点。

在第二个测试用例中,如果我们删除顶点$$$2$$$,我们可以保存顶点$$$3$$$和$$$4$$$。