← 返回题目列表

Codeforces · 1042/F

F. 叶子套装

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

给你一棵无向树,由 $$$n$$$ 个顶点组成。

如果该顶点恰好有一个与其相邻的顶点,则该顶点称为叶子。

某对顶点之间的距离是它们之间的最短路径中的边数。

如果一组叶子中任意一对叶子之间的最大距离小于或等于 $$$k$$$,我们就称该组叶子为漂亮。

您想要将所有叶子分割成不相交的漂亮集合。这种分组的最少组数是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le n \le 10^6$$$, $$$1 \le k \le 10^6$$$) — 树中的顶点数以及每个美丽集合中任意一对叶子之间的最大距离。

接下来的 $$$n - 1$$$ 行包含两个整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — 第 $$$i$$$ 条边的描述。

保证给定的边形成一棵树。

输出

打印一个整数 - 分割可以拥有的漂亮集合的最小数量。

示例

输入 #1

9 3
1 2
1 3
2 4
2 5
3 6
6 7
6 8
3 9

输出 #1

2

输入 #2

5 3
1 2
2 3
3 4
4 5

输出 #2

2

输入 #3

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

输出 #3

5

注意

这是第一个示例的图表: