BZOJ1912[APIO2010]patrol巡逻
时间：2017-01-17 16:56:51
收藏：0
阅读：266
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
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。
题解：
对于新建的k条边，求出在原树上的k条路径；若其无重复边，则
题意即在树上求k条边不重复路径，时总距离最长（若重复则视为重复部分不被选，则又重组为两条不重复路径。
原文：http://www.cnblogs.com/GhostReach/p/6293713.html
评论（0）