305637: CF1067B. Multihedgehog
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Multihedgehog
题意翻译
【题意简述】\ 定义一棵树 k-multihedgehog: 对于 1-multihedgehog,其中一个点度数 $\ge3$ ,其它点度数均为 $1$. k-multihedgehog 是在 k-1-multihedgehog 的基础上,把所有度为 $1$ 的点替换成一个 1-multihedgehog 并与原图相连。题目描述
Someone give a strange birthday present to Ivan. It is hedgehog — connected undirected graph in which one vertex has degree at least $ 3 $ (we will call it center) and all other vertices has degree 1. Ivan thought that hedgehog is too boring and decided to make himself $ k $ -multihedgehog. Let us define $ k $ -multihedgehog as follows: - $ 1 $ -multihedgehog is hedgehog: it has one vertex of degree at least $ 3 $ and some vertices of degree 1. - For all $ k \ge 2 $ , $ k $ -multihedgehog is $ (k-1) $ -multihedgehog in which the following changes has been made for each vertex $ v $ with degree 1: let $ u $ be its only neighbor; remove vertex $ v $ , create a new hedgehog with center at vertex $ w $ and connect vertices $ u $ and $ w $ with an edge. New hedgehogs can differ from each other and the initial gift. Thereby $ k $ -multihedgehog is a tree. Ivan made $ k $ -multihedgehog but he is not sure that he did not make any mistakes. That is why he asked you to check if his tree is indeed $ k $ -multihedgehog.输入输出格式
输入格式
First line of input contains $ 2 $ integers $ n $ , $ k $ ( $ 1 \le n \le 10^{5} $ , $ 1 \le k \le 10^{9} $ ) — number of vertices and hedgehog parameter. Next $ n-1 $ lines contains two integers $ u $ $ v $ ( $ 1 \le u, \,\, v \le n; \,\, u \ne v $ ) — indices of vertices connected by edge. It is guaranteed that given graph is a tree.
输出格式
Print "Yes" (without quotes), if given graph is $ k $ -multihedgehog, and "No" (without quotes) otherwise.
输入输出样例
输入样例 #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