原题：洛谷P3629
问题转化
首先，给定的图是一个有 \(n\) 个点，\(n-1\) 条边的无向连通图，这个图就等价于一棵树。
不建立新的道路时，从 \(1\) 号节点出发，把整棵树上的每条边遍历至少一次，再回到 \(1\) 号节点，会恰好经过每条边两次，路线总长度为 \(2(n-1)\)，如下图最左边的部分所示。根据树的深度优先遍历的思想，很容易证明这个结论，因为每条边必然被递归一次、回溯一次。
建立 \(1\) 条新道路之后，因为新道路必须经过恰好一次（\(0\) 次、\(2\) 次都不可以），所以在沿着新道路 \((x,y)\) 巡逻之后，要返回 \(x\)，就必须沿着树上从 \(y\) 到 \(x\) 的路径巡逻一遍，最终形成一个环。与不建立新道路的情况相结合，相当于树上 \(x\) 与 \(y\) 之间的路径就只需经过一次了，如上图所示。
因此，当 \(K=1\) 时，我们找到树的最长链，在两个端点之间加一条新道路，就能让总的巡逻距离最小。，答案就是 \(2(n-1)-l+1\)。
当 \(K=2\) 时，建立第 \(2\) 条新道路 \((u,v)\) 之后，又会形成一个环，若两条新道路形成的环不重叠，则树上 \(u,v\) 之间的路径只需经过一次，答案继续减小。否则，在两个环重叠的情况下，如果我们还按照刚才的方法把第 \(2\) 个环与建立 \(1\) 条新道路的情况相结合，两个换重叠的部分就不会被巡逻到，如下图所示。因为题目要求每条道路必须被巡逻，两个环重叠的部分就不会被巡逻到，并且返回。最终的结果应是两个环重叠的部分由 “只需经过一次” 变回了 “需要经过两次”。
综上所述，我们得到了如下算法。
\(1.\) 在最初的树上求直径，设直径为 \(l_1\)。然后把直径上的边权取反（从 \(1\) 改为 \(-1\)）。
\(2.\) 在最长链边权取反后的树上再次求直径，设直径为 \(l_2\)。
答案就是 \(2(n-1)-(l_1-1)-(l_2)-1=2n-l_1-l_2\)。如果这条直径包含 \(l_1\) 取反的部分，就相当于两个环重叠。减掉 \((l_1-1)\) 后，重叠的部分变成了 “只需经过一次”，减掉 \((l_2-1)\) 后，相当于把重叠的部分加回来，变为 “需要经过两次”，与我们之前的讨论相符。时间复杂度为 \(O(n)\)。
以上摘编自李煜东《算法竞赛进阶指南》
处理 \(l_1\) 的路径
书中处理 \(l_1\) 的路径时用的是两次 \(\operatorname{BFS}\)，而我们也可以用 \(\operatorname{LCA}\) 来处理，原理如下：
我们在处理 \(l_1\) 时可以同时处理出 \(l_1\) 的起点 \(st\) 和终点 \(ed\)。由于树上两点间的路径是唯一的，且这个路径一定经过这两点的 \(\operatorname{LCA}\)。所以用树形 \(\operatorname{DP}\) 处理完 \(l_1\) 后，求出 \(i\) 和 \(j\) 的 \(\operatorname{LCA}\)，记为 \(x\)。然后先从 \(st\) 开始向父亲节点跳，跳到 \(x\)，将期间经过的点顺序存进数组 \(road\)。再从 \(ed\) 开始跳，跳到 \(x\)，将经过的点逆序存进数组 \(road\)，数组 \(road\) 就是 \(l_1\) 的路径。
如何处理起点和终点呢？很简单，在树形 \(\operatorname{DP}\) 处理 \(D_i\) （从节点 \(i\) 出发走向以 \(i\) 为根的子树，能够到达的最远节点的距离）时，用 \(to_i\) 记录 从节点 \(i\) 出发走向以 \(i\) 为根的子树，能够到达的最远节点。那么对于由 \(D_i,D_j,(i,j)~(j∈son_i)\) 组成的链，它的起点和终点就是 \(to_i\) 和 \(to_j\)。
注意，对 \(to_i\) 的初值的处理应为：对于每个叶节点 \(u\)，\(to_u=u\)。
还有一点要注意的，正常的存边方式无法通过起点和终点确定一条边，但是我们处理出的是路径上的点，只能通过起点和终点给边权取反，所以我们要改一下边权的存储方式：map<int,int>v[N]，\(v_{ij}=w\) 表示从 \(i\) 到 \(j\) 有一条边权为 \(w\) 的边。
vector<int>e[N];
map<int,int>v[N];
inline void work()
{
while(st!=x) v[st][f[st][0]]=v[f[st][0]][st]=-1,st=f[st][0];
while(ed!=x) v[ed][f[ed][0]]=v[f[ed][0]][ed]=-1,ed=f[ed][0];
//这里图省事，不把路径存数组里，在跳的时候直接把边权取反
}
void DP(int u,int num)
{
vis[u]=1;
if(du[u]==1) to[u]=u;//判断叶节点
for(reg int i=0;i<e[u].size();i=-~i)
{
if(vis[e[u][i]]) continue;
DP(e[u][i],num);
if(l[num]<d[u]+d[e[u][i]]+v[u][e[u][i]]) l[num]=d[u]+d[e[u][i]]+v[u][e[u][i]],st=to[u],ed=to[e[u][i]];
if(d[u]<d[e[u][i]]+v[u][e[u][i]]) d[u]=d[e[u][i]]+v[u][e[u][i]],to[u]=to[e[u][i]];
}
}
signed main()
{
n=read();k=read();
for(reg int i=1;i<n;i=-~i)
{
x=read();y=read();
e[x].push_back(y);e[y].push_back(x);
du[x]++;du[y]++;v[x][y]=v[y][x]=1;
}
DP(1,1);
if(k==1) return printf("%lld",2*(n-1)-l[1]+1),0;
pre();dfs(1,0);x=lca(st,ed);//求lca，pre是预处理log
work();
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));//注意清零
DP(1,2);
return printf("%lld",2*n-l[1]-l[2]),0;
}