巡逻

题目内容

题目描述

在一个地区有n个村庄,编号为1到n,有n-1条道路连接着这些村庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其他任意村庄。每条道路的长度均为1个单位。

为了保证该地区的安全,巡警车每天要到所有的道路上巡逻。警察局设在编号为1的村庄里,每天巡警车总是从警察局出发,最终又回到警察局。


在例子给出的地区中,巡警车为了遍历所有的道路,需要走的距离为14个单位,每条道路都需要经过两次。(警车走过1-2-1-3-4-3-5-6-5-7-5-8-5-3-1的路径, 距离=14)

为了减少总巡逻距离,该地区准备在这些村庄之间建立K条新道路,每条新道路可以连接任意两个村庄。两条新道路可以在同一个村庄出发或结束,一条新道路两端可以连接同一个村庄。

由于资金有限,K只可能是1或2。同时,为了不浪费资金,每天巡警车必须经过新建的道路正好一次。

现在请你编写一个程序,计算出最佳的新建道路方案使得总的巡逻距离最小,并输出这个最小的巡逻距离。

输入描述

第一行包含两个整数n和K,其中3≤n≤100,000,1≤K≤2。

接下来n-1行,每行两个整数a、b,表示村庄a和b之间有一条道路。

输出描述

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

样例输入

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

样例输出

11

提示

提交评测
请登录后再操作

题目描述

巡逻
1217
0
Level4
14
11
79%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在