```cpp
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n,k,ans;
int head[N],edge[2*N],nxt[2*N],w[2*N],vis[N],d[N],idx=1;
int c,f[N];
void add(int a,int b,int c){
edge[++idx]=b;
w[idx]=c;
nxt[idx]=head[a];
head[a]=idx;
}
void dp(int x,int fa){
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=edge[i];
if(vis[y]) continue;
if(y==fa) continue;
dp(y,x);
ans=max(ans,d[x]+d[y]+w[i]);
d[x]=max(d[x],d[y]+w[i]);
}
return;
}
void dfs(int x,int fa,int fl){
d[x]=d[fa]+1;
if(d[x]>d[c]) c=x; // **
for(int i=head[x];i;i=nxt[i]){
int y=edge[i];
if(y==fa) continue;
//if(fl) f[x]=i^1;
if(fl) f[y]=i^1; // **
//if(d[y]>d[c]) c=y; // **
dfs(y,x,fl);
}
return;
}
int main(){
cin>>n>>k;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y,1);
add(y,x,1);
}
if(k==0) cout<<2*(n-1);
else if(k==1){
dp(1,0);
cout<<2*(n-1)-ans+1;
}
else{
dfs(1,0,0);
int s=c;
for (int i=1;i<=n;++i) d[i]=0; // **
dfs(s,0,1);
int t=c;
while(c!=s){
int p=f[c];
w[p]=w[p^1]=-1;
c=edge[p];
}
int tmp=d[t]; // **
for (int i=1;i<=n;++i) d[i]=0; // **
dp(1,0);
//cout<<2*n-ans-d[t];
cout<<2*n-ans-tmp+1; // **
}
return 0;
}
```
by liangyanbang @ 2024-07-20 10:46:53
@\_Liyx_
by liangyanbang @ 2024-07-20 10:47:47
@[_Liyx_](/user/1041884)
by liangyanbang @ 2024-07-23 18:09:47
@[liangyanbang](/user/1210353) 啊，这道题已经A了，谢谢
by _Liyx_ @ 2024-07-23 19:12:36