CF2227H Fallen Leaves

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$。

对于每个测试用例，输出一个整数，表示操作结束后可能达到的最小总代价。

在第一个测试用例中，叶子集合 $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 翻译