在一个地区有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条道路后的最小巡逻距离。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15