[POI2006]Met

时间限制:15s      空间限制:162MB

题目描述

给出一棵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


题目来源

没有写明来源

Menuappsclose