CF1593E.Gardener and Tree

A tree is an undirected connected graph in which there are no cycles. This problem is about non-rooted trees. A leaf of a tree is a vertex that is connected to at most one vertex.

The gardener Vitaly grew a tree from $n$ vertices. He decided to trim the tree. To do this, he performs a number of operations. In one operation, he removes all leaves of the tree.

Example of a tree.

For example, consider the tree shown in the figure above. The figure below shows the result of applying exactly one operation to the tree.

The result of applying the operation "remove all leaves" to the tree.

Note the special cases of the operation:

• applying an operation to an empty tree (of $0$ vertices) does not change it;
• applying an operation to a tree of one vertex removes this vertex (this vertex is treated as a leaf);
• applying an operation to a tree of two vertices removes both vertices (both vertices are treated as leaves).

Vitaly applied $k$ operations sequentially to the tree. How many vertices remain?

树是无向连通图，且其中不存在环。本题讨论的是无根树。树的一个叶节点（leaf）是指至多与一个顶点相连的顶点。

园丁 Vitaly 种植了一棵包含 $n$ 个顶点的树。他决定对这棵树进行修剪。为此，他执行若干次操作。每次操作中，他将树的所有叶节点全部移除。

一棵树的示例。

例如，考虑上图所示的树。下图展示了对该树恰好执行一次操作后的结果。

对该树执行“移除所有叶节点”操作后的结果。

注意该操作的几种特殊情况：

• 对空树（含 $0$ 个顶点）执行操作，树保持不变；
• 对仅含一个顶点的树执行操作，该顶点会被移除（该顶点被视为叶节点）；
• 对含两个顶点的树执行操作，两个顶点均被移除（两个顶点均被视为叶节点）。

Vitaly 对该树依次执行了 $k$ 次上述操作。问：最终还剩下多少个顶点？

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

Each test case is preceded by an empty line.

Each test case consists of several lines. The first line of the test case contains two integers $n$ and $k$ ($1 \le n \le 4 \cdot 10^5$, $1 \le k \le 2 \cdot 10^5$) — the number of vertices in the tree and the number of operations, respectively. Then $n - 1$ lines follow, each of them contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) which 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$ from all test cases does not exceed $4 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例之前均有一个空行。

每个测试用例由若干行组成。测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 4 \cdot 10^5$，$1 \le k \le 2 \cdot 10^5$）—— 分别表示树中顶点的数量和操作的数量。接下来是 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示由一条边连接的一对顶点。保证所给图是一棵树，且不含环或重边。

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

For each test case output on a separate line a single integer — the number of vertices that remain in the tree after applying $k$ operations.

对于每个测试用例，在单独一行输出一个整数——即执行 $k$ 次操作后树中剩余的顶点数量。

The first test case is considered in the statement.

The second test case contains a tree of two vertices. $200000$ operations are applied to it. The first one removes all two vertices, the other operations do not change the tree.

In the third test case, a tree of three vertices is given. As a result of the first operation, only $1$ vertex remains in it (with the index $2$), the second operation makes the tree empty.

第一个测试用例已在题目描述中给出。

第二个测试用例包含一棵两个顶点的树。对该树执行 $200000$ 次操作：第一次操作移除了全部两个顶点，其余操作均不改变该树。

第三个测试用例给出了一棵三个顶点的树。在第一次操作后，树中仅剩 $1$ 个顶点（编号为 $2$）；第二次操作使该树变为空。