题目描述

Yousef 得到了一棵 $n$ 个顶点的树 $^{\text{∗}}$，顶点编号为 $1$ 到 $n$。

设 $S$ 为给定树的所有叶子节点 $^{\text{†}}$ 的集合（该集合由原始树确定，不会变化）。

Yousef 重复如下操作，直到未被选择的顶点数不超过 $1$：

• 从 $S$ 中选出两个未被选择过的不同顶点 $u, v$。
• 将 $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$），表示有一条连接顶点 $u$ 和 $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$，总代价加 $2$，$1$ 和 $3$ 标记已选择。
• 选择 $u = 5$，$v = 6$，$d(5, 6) = 2$，总代价再加 $2$，$5$ 和 $6$ 标记已选择。

不存在未被选择的顶点，过程终止，总代价为 $4$。

第二个测试用例对应的树。

由 ChatGPT 5 翻译

来源

Codeforces 2227H，英文题名 Fallen Leaves。