给 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$$$。
输出
对于每个测试用例,输出一个整数 - 流程结束后可实现的最小可能总成本。
示例
输入复制
441 22 32 461 22 32 44 54 671 22 33 42 55 65 751 21 33 43 5
输出复制
2452
注意
在第一个测试用例中,叶子集合 $$$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$$$。
第二个测试用例中的给定树。