rt，第一条直径使用了dfs来求，因为要记录路径，第二条使用dp，因为dfs无法处理负边权

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1e5+100;
int n,tot=1,c,p,q,w,len1,ans,cnt,k,len2;
int to[maxn*2],ne[maxn*2],lin[maxn];
int du[maxn],va[maxn*2],d[maxn],f[maxn];
int a[maxn],b[maxn],flag,vis[maxn];
void add(int u,int v)//建图
{
	du[u]++;
	du[v]++;
	to[++tot]=v;
	ne[tot]=lin[u];
	lin[u]=tot;
	va[tot]=1;
}
void dfs(int s,int step)
{
	a[++cnt]=s;
	if(du[s]==2&&s!=p)//判叶节点
	{
		if(ans<step)
		{
			ans=step;
			w=s;
			for(int i=1;i<=cnt;i++)
			b[i]=a[i];//记录直径路径
			c=cnt;
		}
		return;
	}
	for(int i=lin[s];i;i=ne[i])
	{
		int x=to[i];
		if(vis[x]==0)
		{
			vis[x]=1;
			dfs(x,step+va[i]);
			cnt--;
			vis[x]=0;
		}
		
	}
}
void dp(int x)
{
	vis[x]=1;
	for(int i=lin[x];i;i=ne[i])
	{
		int y=to[i];
		if(vis[y])
		continue;
		dp(y);
		if(ans<d[x]+d[y]+va[i])
		{
			ans=d[x]+d[y]+va[i];
			a[++c]=y;
		}
		d[x]=max(d[x],d[y]+va[i]);
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			add(x,y);
			add(y,x);
		}
	vis[1]=1;
	ans=0;
	dfs(1,0);
	memset(vis,0,sizeof(vis));
	p=w;
	vis[p]=1;
	ans=0,cnt=0;
    memset(b,0,sizeof(b));
	dfs(p,0);
	len1=ans;
	if(k==2)
	{
		
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=c;i++)//第一条直径边权取反
	{
		vis[b[i]]=1;
		for(int j=lin[b[i]];j;j=ne[j])
		{
			if(i<c)
			if(to[j]==b[i+1]||to[j]==b[i-1])
		 	{
		 		va[j]=va[j^1]=-1;
			}
		 	if(i==c)
		 	if(to[j]==b[i-1])
		 	{
		 		va[j]=va[j^1]=-1;
			 }
		}
		
	}
	memset(vis,0,sizeof(vis));
	ans=-1;
	dp(1);
	len2=ans;
	printf("%d",2*n-len1-len2);
	}
	else printf("%d",2*(n-1)-len1+1);
	
	return 0;
}