好的，这是整理好的题面，不含解题思路，只包含样例解释。

题目描述

在一个地区有 $n$ 个村庄，编号 $1,2,\dots,n$。
有 $n-1$ 条道路连接这些村庄，每条道路刚好连接两个村庄，且从任何一个村庄都可以通过这些道路到达其他任一个村庄（即这些道路构成一棵树）。
每条道路的长度均为 $1$ 单位。

警察局设在编号为 $1$ 的村庄里。
每天巡警车要从警局出发，经过所有道路至少一次，最后回到警局。
巡逻距离即巡警车走过的总长度。

为了减少巡逻距离，该地区准备在这些村庄之间建立 $K$ 条新的道路，每条新道路可以连接任意两个村庄（允许新道路在一个村庄会合或结束，甚至允许是环）。
但是资金有限，$K$ 只能是 $1$ 或 $2$。

同时，为了不浪费资金，每天巡警车必须经过新建的道路正好一次（即新建的道路每天巡逻一次，不能走多次，也不能不走）。

请你计算：在给定村庄间道路信息和 $K$ 的情况下，选择最佳的新建道路方案，使得总的巡逻距离最小。

输入格式

第一行包含两个整数 $n$ 和 $K$。
接下来 $n-1$ 行，每行两个整数 $a$ 和 $b$，表示村庄 $a$ 和 $b$ 之间有一条道路。

输出格式

输出一个整数，表示新建 $K$ 条道路后能达到的最小巡逻距离。

数据范围

• $3 \le n \le 100000$
• $1 \le K \le 2$
• $1 \le a, b \le n$

输入样例

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

输出样例

11

样例解释

$n=8$，$K=1$，原树结构（每条边长度 1）：

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

这个树形状大致为： 1 连接 2 和 3；
3 连接 4 和 5；
5 连接 6、7、8。

不加新路时：
巡逻所有边至少一次并返回起点，每条原树边必须走两次（因为要回到起点 1）。
原树边数 $n-1=7$，所以总巡逻距离 $= 2\times 7 = 14$。

新建一条道路 $K=1$：
新路必须走恰好一次，且新路连接任意两个点。
加入新路后，会形成一个环，可以让巡逻车少走一些原树边的重复路径。

最佳方案：
新路连接 1 和 8（或者连接其他相距较远的两个端点），这样形成一个环（1-3-5-8 和 新路 8-1）。
此时巡逻路线可以设计为：
从 1 出发，走新路到 8，然后走 8-5-3-1-2-1-3-4-3-5-6-5-7-5-3-1（这个顺序需要详细安排，但目的是使总长最小）。
经过计算，最优新路能减少的巡逻距离 = 原树中最长路径（直径）的长度，减少 $L$（直径长），然后因为要多走一次新路长度 1，所以净减少 $L-1$。

此树中，直径两端点可以取 6 和 7（或 6 和 4 等），通过计算得直径长度 $L = 5$（例如 6-5-3-1-2 路径长度为 4 条边，即距离 4？不对，这里需要具体算：从 6 到 2 是 6-5-3-1-2，边数 4，距离 4；检查是否有更长的，比如 4 到 7：4-3-5-7，边数 3；4 到 8：4-3-5-8，边数 3；最长应是 6 到 7：6-5-7，边数 2，很短。所以需要求树的直径）。
手动求直径：
以 1 为根：最远点可能是 6（1-3-5-6，距离 3），或者 4（1-3-4，距离 2）。
实际直径端点可能为 2 和 6：路径 2-1-3-5-6，距离 4。
检查有没有更长：尝试 4 到 7：4-3-5-7，距离 3；4 到 8：4-3-5-8，距离 3。
2 到 7：2-1-3-5-7，距离 4。
2 到 8：2-1-3-5-8，距离 4。
可能直径就是 4。

于是减少的距离 = $4-1=3$。
总巡逻距离 $= 14 - 3 = 11$。

所以输出 11。

注意：实际直径需要程序计算，上述手工估算只是说明样例输出 11 的来源。