[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。
题目来源
没有写明来源