UOJ Logo Universal Online Judge

UOJ

附件下载 统计

English Problem Statement

为了防止电网损坏,跳蚤国的电网需要定期检修。

跳蚤国的电网由 n 个结点和 n1 条电线组成,结点标号为 1,2,,n。每条电线连接了两个不同的结点,且所有的结点都是相互连通的。

伏特和欧姆初始都在 1 号结点,接下来的每一秒,伏特 欧姆会沿着某一条电线移动到相邻的结点。为了检修电网,现在每个结点都至少要被伏特 欧姆到达一次。

两人为了保持通信,在任意时刻两人的距离都不能超过 k。两个人的距离定义为伏特到达欧姆的位置至少需多少次移动。

现在伏特想知道,两人为了完成电网的检修,至少需要多少秒?可以证明两人能在约束条件下完成电网的检修。

输入格式

第一行输入两个正整数 n,k

接下来 n1 行,每行两个正整数 u,v 表示一条连接结点 u 和结点 v 的电线。

输出格式

一行一个非负整数,表示检修电网至少需要的时间。

样例一

input

4 1
1 2
1 3
3 4

output

5

explanation

最优策略如下:

  • 1 秒伏特从结点 1 移动到结点 2

  • 2 秒伏特从结点 2 移动到结点 1

  • 3 秒欧姆从结点 1 移动到结点 3

  • 4 秒伏特从结点 1 移动到结点 3

  • 5 秒欧姆从结点 3 移动到结点 4

不难发现两人距离始终保持在 1 内。

样例二

input

5 4
1 2
1 3
2 4
3 5

output

4

explanation

最优策略如下:

  • 1 秒伏特从结点 1 移动到结点 2

  • 2 秒伏特从结点 2 移动到结点 4

  • 3 秒欧姆从结点 1 移动到结点 3

  • 4 秒欧姆从结点 3 移动到结点 5

由于 k=4,相当于对两人的距离没有限制。

样例三~五

见附件下载。

限制与约定

对于所有数据,保证 1k<n106

子任务编号 n 子任务分值
1 18 8
2 500 12
3 2000 16
4 2×105 24
5 106 40

时间限制:2s

空间限制:512MB