容易发现，当加一条边时，树上会形成一个环，这个环上的每个点都是只要走一次的，也就是说我们的答案减少了这个环上点的个数，要使答案最小，即要使环上的点最多，求出直径\(L\)，则答案为\(2(n-1)-L+1\)。
当加两条边时，同样会形成一个新环，但这个新环可能和第一个环有交点，而这些交点仍是要走两次的，所以我们要让交点的个数尽可能小，所以，把原直径上的所有边权取反，代表若取了这条边，答案会增大那么多，然后再求一次树的直径\(L_1\)，则答案为\(2(n-1)-L+1-L_1+1=2n-L-L_1\)。
注意，第二次求直径不能用两边\(DFS/BFS\)来求，因为树中有负权边，直接跑答案显然是错的，所以我们要用树形\(DP\)求直径。
#include <cstdio>
const int MAXN = 5000010;
namespace IO{
inline int read(){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
return s * w;
}
}using namespace IO;
namespace G{
struct Edge{
int next, to, dis;
}e[MAXN << 1];
int head[MAXN], num;
inline void Add(int from, int to, int dis){
e[++num].to = to;
e[num].dis = dis;
e[num].next = head[from];
head[from] = num;
}
}using namespace G;
int n, k, s, t;
int a, b;
int pre[MAXN];
int Max = 0;
inline int max(int a, int b){
return a > b ? a : b;
}
void dfs(int u, int fa, int dep){
if(dep > Max && fa) s = u, Max = dep;
for(int i = head[u]; i; i = e[i].next)
if(e[i].to != fa)
dfs(e[i].to, u, dep + e[i].dis);
}
void DFS(int u, int fa, int dep){
if(dep > Max) t = u, Max = dep;
for(int i = head[u]; i; i = e[i].next)
if(e[i].to != fa)
pre[e[i].to] = u, DFS(e[i].to, u, dep + e[i].dis);
}
int d[MAXN], ans = -2147483647;
void dp(int u, int fa){
for(int i = head[u]; i; i = e[i].next)
if(e[i].to != fa){
dp(e[i].to, u);
ans = max(ans, d[u] + d[e[i].to] + e[i].dis);
d[u] = max(d[u], d[e[i].to] + e[i].dis);
}
}
int main(){
n = read(); k = read();
for(int i = 1; i < n; ++i){
a = read(); b = read();
Add(a, b, 1); Add(b, a, 1);
}
Max = -2147483647; dfs(1, 0, 0);
Max = -2147483647; DFS(s, 0, 0);
if(k == 1){
printf("%d\n", (n << 1) - 1 - Max);
return 0;
}
int now = t;
while(now != s){
for(int i = head[now]; i; i = e[i].next)
if(e[i].to == pre[now]){
e[i].dis = -1;
break;
}
now = pre[now];
}
dp(t, 0);
printf("%d\n", (n << 1) - Max - ans);
return 0;
}