Miku

很好的坑题，务必注意因为负边权和求路径的问题，这里需要同时用到两种方法，搜索和dp。

对于原来的情况，事实上就是每一条边都要走两次，（毕竟你还要回来啊）

但是你要是建了一条边，就会形成一个环，那么这辆车就可以直接走回去了（沿着这个圈回到出发点，也就是说，少了一条边长度的距离）

那么怎么搞呢，当然是Ko no 直径啊

建第二条边怎么搞呢？倘若说没有重叠部分，那么就是找呗

但是有重叠怎么办？

有重叠的边重叠部分不但不能少走，反而还要多走啊，这样的话，事实上“贡献”（是对减少长度的贡献）是个-1

所以说把第一次的直径取反就行了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
int ans;
using namespace std;
int q[100001];
int pp;
int n,k;
int l,r;
int temx;
int dis[100001];
int vis[100001];
int dp[100001];
int ma[160][160] ;
struct b{
    int f;
    int to;
    int ne;
    int v;
}ed[200001];
int x,y;
int p;
int head[100001];
void add(int f,int to,int v){
    p++;
    ed[p].f=f;
    ed[p].to=to;
    ed[p].ne=head[f];
    ed[p].v=v;
    head[f]=p;
    return ;
}
void maxx(int x){
    if(dis[x]>dis[temx]){
        temx=x;
    }
    return ; 
}
void emp(){
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    temx=0;
    return ;
}
void dfs(int now,int f){
    vis[now]=1;
    for(int i=head[now];i;i=ed[i].ne){ 
        if(vis[ed[i].to]==1)
        continue;
        dis[ed[i].to]=dis[now]+ed[i].v;
        maxx(ed[i].to);
        dfs(ed[i].to,now);
     } 
    return ;
}
int ff;
void dfss(int now,int f){
    vis[now]=1;
    q[++pp]=now;
    if(now==r||ff){
        ff=1;
        return ;
    }
    for(int i=head[now];i;i=ed[i].ne){ 
        if(vis[ed[i].to]==1||ff)
        continue;
        dis[ed[i].to]=dis[now]+ed[i].v;
        dfss(ed[i].to,now);
    } 
    if(!ff)
    pp--;
    return ;
}
void deal(){
     for(int i=1;i<=pp;++i){
        int u=q[i];
        for(int j=head[u];j;j=ed[j].ne){
            if(ed[j].to==q[i-1]||ed[j].to==q[i+1]){
                ed[j].v=-1;
             }
        }
    }
    return ;
}
void work(int now,int f){
    for(int i=head[now];i;i=ed[i].ne){
        if(ed[i].to==f){
            continue;
        }
        work(ed[i].to,now);
        temx=max(temx,dp[now]+dp[ed[i].to]+ed[i].v);
        dp[now]=max(dp[now],dp[ed[i].to]+ed[i].v);
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y,1);
        add(y,x,1);
    }
    ans=n*2-2;
    dfs(1,0);
    l=temx;
    emp();
    dfs(l,0);
    r=temx;
    emp();
    dfss(l,0);
    ans=ans-pp+2; 
    //这里的pp是点的数量    
    if(k==1){
        cout<<ans;
        return 0;
    }
    deal();
    work(1,-1);
    ans=ans-temx+1;
    cout<<ans; 
    return 0;
}