路由器

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 routea.in 输出文件 routea.out

Farmer John 最近买了些新电脑，它向为奶牛们提供上网的机会，但是上网需要路由器，FJ想尽量少买路由器。FJ 有N个 (1 <= N <= 100,000)(编号为1..N)个农场，由 N-1 条长度是1的边连接起来，没有环. FJ 可以决定把路由器放在哪些农场. 每个农场只有长度为 K (0 <= K <= 10)的网线，该农场可以连接到距离小于等于K的路由器.  路由器本身已经可以连接到互连网，可以被放置到任意的农场.

FJ至少要买多少个路由器，才能让每个农场都能上网？农场想要上网的话，至少要连接到一个包含路由器的农场.

输入格式:

  • 第1行:两个整数: N 和 K
  • 第 2..N行: 每行两个整数，表示两个农场之间有长度为1的边.

样例输入 ( routea.in): 


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


输入解释:

有8个农场.  农场3和农场6有长度为1的边,等等

每个农场的网线最远只能够连接到2个单位长度的农场.

输出格式:


  • 第1行:一个整数，FJ至少需要买多少个路由器.


样例输出 routea.out: 

2