[Apio2010]patrol 巡逻

时间限制:4s      空间限制:64MB

题目描述


输入格式

第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行,每行两个整数 a, b, 表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。


输出格式

输出一个整数,表示新建了K 条道路后能达到的最小巡逻距离。


样例输入

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

样例输出

11

提示

10%的数据中,n ≤ 1000, K = 1; 30%的数据中,K = 1; 80%的数据中,每个村庄相邻的村庄数不超过 25; 90%的数据中,每个村庄相邻的村庄数不超过 150; 100%的数据中,3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。


题目来源

没有写明来源