#1517. [POI2006]Met

题目描述

给出一棵N个结点的树，选择L条路径，覆盖这些路径上的结点，使得被覆盖到的结点数最多。

输入格式

第一行两个正整数N、L(2 <= N <= 1,000,000, 0 <= L <= N)。下面有N-1行，每行两个正整数A和B(1 <= A, B <= N)，表示一条边(A,B)。

输出格式

一个整数，表示最多能覆盖到多少结点。

样例

样例输入

17 3  

1 2  

3 2  

2 4  

5 2  

5 6  

5 8  

7 8  

9 8  

5 10  

10 13  

13 14  

10 12  

12 11  

15 17  

15 16  

15 10  

样例输出

13  

数据范围与提示

鸣谢Oimaster