CF1566E.Buds Re-hanging

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex $v$ (different from root) is the previous to $v$ vertex on the shortest path from the root to the vertex $v$. Children of the vertex $v$ are all vertices for which $v$ is the parent.

A vertex is a leaf if it has no children. We call a vertex a bud, if the following three conditions are satisfied:

• it is not a root,
• it has at least one child, and
• all its children are leaves.

You are given a rooted tree with $n$ vertices. The vertex $1$ is the root. In one operation you can choose any bud with all its children (they are leaves) and re-hang them to any other vertex of the tree. By doing that you delete the edge connecting the bud and its parent and add an edge between the bud and the chosen vertex of the tree. The chosen vertex cannot be the bud itself or any of its children. All children of the bud stay connected to the bud.

What is the minimum number of leaves it is possible to get if you can make any number of the above-mentioned operations (possibly zero)?

树是无环的连通图。有根树具有一个特殊的顶点，称为根。顶点 $v$（非根）的父节点是指从根到 $v$ 的最短路径上位于 $v$ 之前的那个顶点。顶点 $v$ 的子节点是指所有以 $v$ 为父节点的顶点。

若一个顶点没有子节点，则称其为叶节点。若一个顶点满足以下三个条件，则称其为芽节点（bud）：

• 它不是根节点；
• 它至少有一个子节点；
• 它的所有子节点均为叶节点。

给定一棵含 $n$ 个顶点的有根树，其中顶点 $1$ 为根。一次操作定义为：任选一个芽节点及其所有子节点（这些子节点均为叶节点），并将该芽节点（连同其全部子节点）重新挂接到树中任意其他顶点上。具体而言，该操作会删除芽节点与其父节点之间的边，并在芽节点与所选顶点之间添加一条新边。所选顶点不能是该芽节点本身，也不能是它的任意一个子节点。芽节点的所有子节点仍保持与该芽节点相连。

在允许执行任意次数（包括零次）上述操作的前提下，所能得到的叶节点数的最小值是多少？

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of the vertices in the given tree.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) meaning that there is an edge between vertices $u$ and $v$ in the tree.

It is guaranteed that the given graph is a tree.

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

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示给定树中顶点的数量。

接下来的 $n-1$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，且 $u \neq v$），表示树中顶点 $u$ 与 $v$ 之间存在一条边。

保证所给图是一棵树。

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

For each test case print a single integer — the minimal number of leaves that is possible to get after some operations.

对于每个测试用例，输出一个整数——经过若干次操作后可能得到的最少叶子节点数量。

In the first test case the tree looks as follows:

Firstly you can choose a bud vertex $4$ and re-hang it to vertex $3$. After that you can choose a bud vertex $2$ and re-hang it to vertex $7$. As a result, you will have the following tree with $2$ leaves:

It can be proved that it is the minimal number of leaves possible to get.

In the second test case the tree looks as follows:

You can choose a bud vertex $3$ and re-hang it to vertex $5$. As a result, you will have the following tree with $2$ leaves:

It can be proved that it is the minimal number of leaves possible to get.

在第一个测试用例中，树的结构如下所示：

首先，你可以选择芽点顶点 $4$，并将其重新挂接到顶点 $3$ 上；接着，你可以选择芽点顶点 $2$，并将其重新挂接到顶点 $7$ 上。最终得到如下具有 $2$ 个叶子的树：

可以证明，这是所能达到的最少叶子数。

在第二个测试用例中，树的结构如下所示：

你可以选择芽点顶点 $3$，并将其重新挂接到顶点 $5$ 上。最终得到如下具有 $2$ 个叶子的树：

可以证明，这是所能达到的最少叶子数。