CF2018C.Tree Pruning

你有一棵以 $1$ 号节点为根的树，共有 $n$ 个节点。在本题中，叶子节点指的是度数为 $1$ 且不是根节点的节点。

每次操作，你可以移除一个叶子节点及其与树相连的那条边（这样可能会产生新的叶子节点）。你需要进行最少多少次操作，才能使得这棵以 $1$ 号节点为根的树的所有叶子节点都处于距离根节点相同的位置？

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 5 \cdot 10^5$），表示节点数。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示一条连接 $u$ 和 $v$ 的边。保证给出的边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示达到目标所需的最小操作次数。

在前两个示例中，树的结构如下：

在第一个示例中，通过移除边 $(1, 3)$ 和 $(2, 5)$，最终树的所有叶子节点（节点 $6$ 和 $7$）都处于距离根节点（节点 $1$）为 $3$ 的位置。答案为 $2$，即最少需要移除的边数。

在第二个示例中，移除边 $(1, 4)$ 和 $(5, 7)$ 后，所有叶子节点（节点 $4$ 和 $5$）都处于距离根节点（节点 $1$）为 $2$ 的位置。

由 ChatGPT 4.1 翻译