← 返回题目列表

Codeforces · 1593/E

E. 园丁和树

中文机器翻译题面 查看原题

树是一种无向连通图,其中没有循环。这个问题是关于无根树的。树的叶子是最多连接到一个顶点的顶点。

园丁 Vitaly 从 $$$n$$$ 个顶点种了一棵树。他决定修剪这棵树。为此,他执行了许多操作。在一次手术中,他除去了树上的所有叶子。

树的示例。

例如,考虑上图所示的树。下图显示了对树仅应用一项操作的结果。

对树应用“删除所有叶子”操作的结果。

注意操作的特殊情况:

- 对空树($$$0$$$ 顶点)应用操作不会改变它;
- 对一个顶点的树应用操作会删除该顶点(该顶点被视为叶子);
- 对两个顶点的树应用操作会删除两个顶点(两个顶点都被视为叶子)。

Vitaly 按顺序对树应用 $$$k$$$ 操作。还剩下多少个顶点?

输入

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

输出

对于每个测试用例在单独的行上输出一个整数 - 应用 $$$k$$$ 操作后保留在树中的顶点数。

示例

输入 #1

6

14 1
1 2
2 3
2 4
4 5
4 6
2 7
7 8
8 9
8 10
3 11
3 12
1 13
13 14

2 200000
1 2

3 2
1 2
2 3

5 1
5 1
3 2
2 1
5 4

6 2
5 1
2 5
5 6
4 2
3 4

7 1
4 3
5 1
1 3
6 1
1 7
2 1

输出 #1

7
0
0
3
1
2

注意

声明中考虑第一个测试用例。

第二个测试用例包含一个有两个顶点的树。 $$$200000$$$ 操作被应用到它。第一个操作删除所有两个顶点,其他操作不会更改树。

在第三个测试用例中,给出了具有三个顶点的树。第一个操作的结果是,只剩下 $$$1$$$ 顶点(索引为 $$$2$$$),第二个操作使树为空。