CF1905B Begginer's Zelda

给定一棵树 $^{\dagger}$。在一次 zelda 操作中，你可以进行如下操作： - 选择树上的两个顶点 $u$ 和 $v$； - 将从 $u$ 到 $v$ 的路径上的所有顶点压缩成一个顶点。换句话说，从 $u$ 到 $v$ 路径上的所有顶点都会从树中被删除，创建一个新的顶点 $w$。然后，所有原本与该路径上某个顶点有边相连的顶点 $s$，都会与新顶点 $w$ 相连。  上图展示了对顶点 $1$ 和 $5$ 执行一次 zelda 操作的示意图。请你判断，为了使树中只剩下一个顶点，最少需要执行多少次 zelda 操作。 $^{\dagger}$ 一棵树是一个连通且无环的无向图。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示树的顶点数。 接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \ne v_i$），表示第 $i$ 条边连接的两个顶点编号。 保证给定的边构成一棵树。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。

对于每组测试数据，输出一个整数，表示使树中只剩下一个顶点所需的最少 zelda 操作次数。

在第一个测试用例中，只需对顶点 $2$ 和 $4$ 执行一次 zelda 操作即可。 在第二个测试用例中，可以按如下方式执行 zelda 操作： 1. $u = 2, v = 1$。新生成的顶点记为 $w = 10$； 2. $u = 4, v = 9$。新生成的顶点记为 $w = 11$； 3. $u = 8, v = 10$。执行完该操作后，树中只剩下一个顶点。 由 ChatGPT 4.1 翻译