Problem 1912. -- [Apio2010]patrol 巡逻 -- 衡阳八中OJ离线版-2014-11-04

F.A.Qs	Home	ProblemSet	Status	Ranklist	Contest	Login	Register	捐赠本站

Notice:开心刷题：）

1912: [Apio2010]patrol 巡逻

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 496 Solved: 288
[Submit][Status]

第一行包含两个整数 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

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