A30824.Gold King的小宝贝

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Gold King在一天清晨醒来,发现他的小宝贝-仓鼠逃脱了。他在房间里找啊找,但没有找到。他试着用一些奶酪来诱捕仓鼠,他把奶酪夹在房间里,等待了三天,除了蟑螂,什么都没发现。
他打开小区的地图,发现没有循环路径,并且可以从他的房间到达小区的每个位置。陷阱在地图中有这样的作用,如果仓鼠仍在离陷阱距离D的地方,它总是会回来的。你的任务是帮助Gold King在小区的地图上找到仓鼠可能找到的几个位置。假设仓鼠仍藏在小区的某个地方,并且每个相邻位置之间的距离始终是一个距离单位。

输入格式

输入第一行都有两个正整数N(0 <N <= 100000)和D(0 <D <N),以单个空格分隔。N是小区中地点的数量,D是陷阱的有效距离。以下N-1条线描述了地图,每条线都有两个整数x和y(0 <= x,y <N),以一个空格隔开,这意味着x和y在地图中相邻。Gold King的房间始终位于位置0。

输出格式

输出在一行上,输出可能在小区中找到仓鼠的位置数量。

输入输出样例

  • 输入#1

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

    输出#1

    2
    
首页