#258. 巡逻

巡逻

题目描述

一棵单位边权树的1号点为警局。增加恰好 K 条长度为1的新边,新边可连接任意两点,也可为自环。巡逻从1号点出发并回到1号点,覆盖所有原边至少一次,并经过每条新边恰好一次。求最短巡逻距离。

输入格式

首行 n、K,K 为1或2;随后 n−1 条树边。

输出格式

输出最短巡逻距离。

样例输入

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

样例输出

11

题意整理;原题与输入输出格式对照。