第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行，每行两个整数 a, b， 表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。

输出一个整数，表示新建了K 条道路后能达到的最小巡逻距离。

8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6

11

10%的数据中，n ≤ 1000, K = 1； 
30%的数据中，K = 1； 
80%的数据中，每个村庄相邻的村庄数不超过 25； 
90%的数据中，每个村庄相邻的村庄数不超过 150； 
100%的数据中，3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

#define maxn 100010

int n,k,ans,zj,s;

struct EdgeNode{int next,to,len;}edge[maxn<<];

int head[maxn],cnt=;int road[maxn]={},croad[maxn]={};

void add(int u,int v,int w)

{

    cnt++;

    edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].len=w;

}

void insert(int u,int v,int w) {add(u,v,w); add(v,u,w);}

int DFS(int now,int fa)

{

    int maxd=,cmaxd=;

    for (int i=head[now]; i; i=edge[i].next)

        if (edge[i].to!=fa)

            {

                int len=DFS(edge[i].to,now)+edge[i].len;

                if (len>maxd) cmaxd=maxd,maxd=len,croad[now]=road[now],road[now]=i;

                else if (len>cmaxd) cmaxd=len,croad[now]=i;

            }

    if (maxd+cmaxd>zj) zj=maxd+cmaxd,s=now;

//    printf("%d %d %d %d\n",now,fa,maxd,cmaxd);

    return maxd;

}

int main()

{

    n=read(); k=read();

    for (int u,v,i=; i<=n-; i++) u=read(),v=read(),insert(u,v,);

    DFS(,); ans=*(n-)-zj+;

    if (k==)

        {

            for (int i=road[s]; i; i=road[edge[i].to]) edge[i].len=edge[i^].len=-;

            for (int i=croad[s]; i; i=road[edge[i].to]) edge[i].len=edge[i^].len=-;

            zj=; DFS(,); ans=ans-zj+;

        }

    printf("%d\n",ans);

    return ;

}