← 返回题目列表

Codeforces · 2227/H

H. 落叶

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

给 Yousef 一棵树$$$^{\text{*}}$$$,其顶点数为 $$$n$$$,编号从 $$$1$$$ 到 $$$n$$$。

令 $$$S$$$ 为给定树的所有叶子 $$$^{\text{†}}$$$ 的集合(该集合由原始树确定并且不会改变)。

Yousef 重复以下过程,直到未选择的顶点数为 最多 1 个:

  • 选择之前未选择过的两个不同的顶点 $$$u, v \in S$$$。
  • 将 $$$d(u, v)$$$ 添加到总成本中,其中 $$$d(u, v)$$$ 是 $$$u$$$ 和 $$$v$$$ 之间简单路径上的边数。
  • 将 $$$u$$$ 和 $$$v$$$ 标记为已选择。

您的任务是帮助 Yousef 确定流程结束后可实现的最低可能总成本。

$$$^{\text{*}}$$$树是无向连通图,其中不存在循环。

$$$^{\text{†}}$$$树的叶子是最多连接到一个其他顶点的顶点。

输入

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

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

接下来是 $$$n − 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$),描述由边连接的一对顶点。保证给定的图是一棵树并且没有循环或多重边。

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

输出

对于每个测试用例,输出一个整数 - 流程结束后可实现的最小可能总成本。

示例

输入
复制

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

输出
复制

2
4
5
2

注意

在第一个测试用例中,叶子集合 $$$S$$$ 包含 $$$\{1, 3, 4\}$$$。 Yousef 可以执行以下操作:

  • 选择 $$$u = 1$$$、$$$v = 3$$$、$$$d(1, 3) = 2$$$。 Yousef 将 $$$2$$$ 添加到总成本中,并将顶点 $$$1$$$ 和 $$$3$$$ 标记为所选。

由于还有一个顶点未选择,因此该过程停止,总成本为 $$$2$$$。可以证明 $$$2$$$ 是最小答案。

第一个测试用例中的给定树。

在第二个测试用例中,叶子集合 $$$S$$$ 包含 $$$\{1, 3, 5, 6\}$$$。 Yousef 可以执行以下操作:

  • 选择 $$$u = 1$$$、$$$v = 3$$$、$$$d(1, 3) = 2$$$。 Yousef 将 $$$2$$$ 添加到总成本中,并将顶点 $$$1$$$ 和 $$$3$$$ 标记为所选。
  • 选择$$$u = 5$$$,$$$v = 6$$$,$$$d(5, 6) = 2$$$。 Yousef 将 $$$2$$$ 添加到总成本中,并将顶点 $$$5$$$ 和 $$$6$$$ 标记为所选。

由于没有未选择的顶点,因此该过程停止,总成本为 $$$4$$$。

第二个测试用例中的给定树。