← 返回题目列表

Codeforces · 1984/E

E. 随机播放

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

两只饥饿的小熊猫,Oscar 和 Lura,有一棵树 $$$T$$$,有 $$$n$$$ 节点。他们愿意对整棵树 $$$T$$$ 执行一次以下的洗牌过程。通过这个洗牌过程,他们将从旧树的节点中创建一棵新树。

1. 从原始树$$$T$$$中选择任意节点$$$V$$$。创建一棵新树 $$$T_2$$$,以 $$$V$$$ 作为根。
2. 从$$$T$$$中删除$$$V$$$,使得原始树被分成一棵或多棵子树(或者零个子树,如果$$$V$$$是$$$T$$$中的唯一节点)。
3. 使用相同的过程对每个子树进行打乱(再次选择任意节点作为根),然后将所有打乱后的子树的根连接回 $$$V$$$ 以完成构造 $$$T_2$$$。

此后,奥斯卡和卢拉留下了一棵新树$$$T_2$$$。它们只能吃叶子,而且非常饥饿,所以请找出所有树上一次洗牌中可以产生的叶子的最大数量。

请注意,叶子是度数为 $$$1$$$ 的所有节点。因此,如果根只有一个子节点,则可以将其视为叶子。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) - 原始树 $$$T$$$ 中的节点数。

接下来的 $$$n - 1$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$) - 原始树 $$$T$$$ 中的一条边。给定的边形成一棵树。

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

输出

对于每个测试用例,输出一个整数——整棵树上通过一次洗牌过程可实现的最大叶数。

示例

输入 #1

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

输出 #1

4
3
5
6

注意

在第一个测试用例中,可以看出叶子的最大数量是$$$4$$$。为了实现这一点,我们可以选择节点 $$$3$$$ 作为新的根来开始洗牌。

在我们的第二个测试用例中,我们有一行五个节点。可以看出,一次洗牌后叶子的最大数量为$$$3$$$。我们可以从节点 $$$2$$$ 开始,这迫使节点 $$$1$$$ 成为叶子。然后,如果我们选择右侧的节点 $$$4$$$,我们还将有节点 $$$3$$$ 和 $$$5$$$ 作为叶子。

第三个测试用例是具有六个节点的星形图。叶子的数量不能增加,因此我们的答案将是$$$5$$$(如果我们从原始根节点开始洗牌)。