← 返回题目列表

Codeforces · 1067/B

B. 多刺猬

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

有人给伊万一份奇怪的生日礼物。它是刺猬——连通无向图,其中一个顶点的度数至少为 $$$3$$$(我们将其称为中心),而所有其他顶点的度数为 1。 Ivan 认为刺猬太无聊,决定让自己成为 $$$k$$$-multihedgehog。

让我们定义 $$$k$$$-multihedgehog 如下:

- $$$1$$$-multihedgehog 是刺猬:它有一个度数至少为 $$$3$$$ 的顶点和一些度数为 1 的顶点。
- 对于所有 $$$k \ge 2$$$,$$$k$$$-multihedgehog 是 $$$(k-1)$$$-multihedgehog,其中对度数为 1 的每个顶点 $$$v$$$ 进行了以下更改:让 $$$u$$$ 成为其唯一邻居;删除顶点 $$$v$$$,创建一个以顶点 $$$w$$$ 为中心的新刺猬,并用边连接顶点 $$$u$$$ 和 $$$w$$$。新刺猬彼此之间以及最初的礼物可能有所不同。

因此 $$$k$$$-multihedgehog 是一棵树。 Ivan 制作了 $$$k$$$-multihedgehog,但他不确定自己没有犯任何错误。这就是为什么他要求你检查他的树是否确实是$$$k$$$-multihedgehog。

输入

输入的第一行包含 $$$2$$$ 整数 $$$n$$$, $$$k$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le k \le 10^{9}$$$) — 顶点数和刺猬参数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ $$$v$$$ ($$$1 \le u, \,\, v \le n; \,\, u \ne v$$$) — 由边连接的顶点的索引。

保证给定的图是一棵树。

输出

如果给定图形是 $$$k$$$-multihedgehog,则打印“是”(不带引号),否则打印“否”(不带引号)。

示例

输入 #1

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

输出 #1

Yes

输入 #2

3 1
1 3
2 3

输出 #2

No

注意

第一个示例中的 2-multihedgehog 如下所示:

其中心是顶点 $$$13$$$。最后一步创建的刺猬是:[4(中心)、1、2、3]、[6(中心)、7、8、9]、[5(中心)、10、11、12、13]。

第二个示例中的树不是刺猬,因为中心度应至少为 $$$3$$$。