#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
题意整理;原题与输入输出格式对照。
一棵单位边权树的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
题意整理;原题与输入输出格式对照。