8316: 巡逻
[Creator : ]
Description
在一个地区有 n 个村庄,编号为 1,2,…,n。
有 n−1 条道路连接着这些村庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其他任一个村庄。
每条道路的长度均为 1 个单位。
为保证该地区的安全,巡警车每天都要到所有的道路上巡逻。
警察局设在编号为 1 的村庄里,每天巡警车总是从警局出发,最终又回到警局。
为了减少总的巡逻距离,该地区准备在这些村庄之间建立 K 条新的道路,每条新道路可以连接任意两个村庄。
两条新道路可以在同一个村庄会合或结束,甚至新道路可以是一个环。
因为资金有限,所以 K 只能为 1 或 2。
同时,为了不浪费资金,每天巡警车必须经过新建的道路正好一次。
编写一个程序,在给定村庄间道路信息和需要新建的道路数的情况下,计算出最佳的新建道路的方案,使得总的巡逻距离最小。
有 n−1 条道路连接着这些村庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其他任一个村庄。
每条道路的长度均为 1 个单位。
为保证该地区的安全,巡警车每天都要到所有的道路上巡逻。
警察局设在编号为 1 的村庄里,每天巡警车总是从警局出发,最终又回到警局。
为了减少总的巡逻距离,该地区准备在这些村庄之间建立 K 条新的道路,每条新道路可以连接任意两个村庄。
两条新道路可以在同一个村庄会合或结束,甚至新道路可以是一个环。
因为资金有限,所以 K 只能为 1 或 2。
同时,为了不浪费资金,每天巡警车必须经过新建的道路正好一次。
编写一个程序,在给定村庄间道路信息和需要新建的道路数的情况下,计算出最佳的新建道路的方案,使得总的巡逻距离最小。
Input
第一行包含两个整数 n 和 K。
接下来 n−1 行每行两个整数 a 和 b,表示村庄 a 和 b 之间有一条道路。
接下来 n−1 行每行两个整数 a 和 b,表示村庄 a 和 b 之间有一条道路。
Output
输出一个整数,表示新建了 K 条道路后能达到的最小巡逻距离。
Constraints
3≤n≤100,000
1≤K≤2
1≤a,b≤n
1≤K≤2
1≤a,b≤n
Sample 1 Input
8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6
Sample 1 Output
11