CF2227H.Fallen Leaves

Yousef is given a tree$^{\text{∗}}$ of $n$ vertices numbered from $1$ to $n$.

Let $S$ be the set of all leaves$^{\text{†}}$ of the given tree (this set is determined from the original tree and does not change).

Yousef repeats the following process until the number of unchosen vertices is at most one:

• Choose two distinct vertices $u, v \in S$ that have not been chosen before.
• Add $d(u, v)$ to the total cost, where $d(u, v)$ is the number of edges on the simple path between $u$ and $v$.
• Mark $u$ and $v$ as chosen.

Your task is to help Yousef determine the minimum possible total cost achievable after the process ends.

$^{\text{∗}}$A tree is an undirected connected graph in which there are no cycles.

$^{\text{†}}$A leaf of a tree is a vertex that is connected to at most one other vertex.

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

令 $S$ 表示给定树中所有叶子节点$^{\text{†}}$ 的集合（该集合由原始树确定，且在整个过程中保持不变）。

优素福重复执行以下过程，直到未被选中的顶点数至多为 $1$：

• 从 $S$ 中选择两个尚未被选过的不同顶点 $u, v \in S$；
• 将 $d(u, v)$ 加入总代价，其中 $d(u, v)$ 表示 $u$ 与 $v$ 之间唯一简单路径上的边数；
• 将 $u$ 和 $v$ 标记为已选。

你的任务是帮助优素福确定该过程结束时所能达到的最小可能总代价。

$^{\text{∗}}$ 树是一种无向连通图，其中不含任何环。

$^{\text{†}}$ 树的一个叶子节点是指度数至多为 $1$ 的顶点（即仅与至多一个其他顶点相连）。

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of several lines. The first line of the test case contains an integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

Then $n − 1$ lines follow, each of which contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) that describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output a single integer — the minimum possible total cost achievable after the process ends.

对于每个测试用例，输出一个整数——过程结束后所能达到的最小总成本。

In the first test case, the set of leaves $S$ contains ${1, 3, 4}$. Yousef can do the following:

• Choose $u = 1$, $v = 3$, with $d(1, 3) = 2$. Yousef adds $2$ to the total cost and marks vertices $1$ and $3$ as chosen.

Since there is one vertex left unchosen, the process stops, and the total cost is $2$. It can be shown that $2$ is the minimum answer.

The given tree in the first test case.

In the second test case, the set of leaves $S$ contains ${1, 3, 5, 6}$. Yousef can do the following:

• Choose $u = 1$, $v = 3$, with $d(1, 3) = 2$. Yousef adds $2$ to the total cost and marks vertices $1$ and $3$ as chosen.
• Choose $u = 5$, $v = 6$, with $d(5, 6) = 2$. Yousef adds $2$ to the total cost and marks vertices $5$ and $6$ as chosen.

Since there is no vertex left unchosen, the process stops, and the total cost is $4$.

The given tree in the second test case.

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

• 选择 $u = 1$、$v = 3$，此时 $d(1, 3) = 2$。Yousef 将 $2$ 加入总代价，并将顶点 $1$ 和 $3$ 标记为已选。

由于还剩一个顶点（$4$）未被选中，该过程终止，总代价为 $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$。

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