【bzoj1912】[Apio2010]patrol 巡逻

2015年4月9日2,2460

Description

Input

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

Output

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

Sample Input

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

Sample Output

11

HINT

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

题解

这种题都wa了好几发觉得生活失去了希望

k=1,很显然最优的方法就是在树的直径xy之间连一条边,这样xy之间的距离缩短为1,答案为2(n1)len1+1

k=2,将树的直径上的所有边权全部标为-1,再求一次直径len2,答案为2(n1)len1+1len2+1