[HOJ] 237 - Patrol

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define N 100005
int vi[N]={0},tmp=0,p,flag=0;
vector<int> s[N],arr,que;
void dfs(int u,int add){
    if(flag) arr.push_back(u);
    if(add>tmp){
        tmp=add;
        p=u;
    }
    int i;
    for(i=0;i<s[u].size();i++){
        int v=s[u][i];
        if(vi[v]==0){
            vi[v]=1;
            dfs(v,add+1);
            if(flag) arr.pop_back();
            vi[v]=0;
        }
    }
    if(flag && add==tmp){
        que=arr;
        flag=0;
    }
    return;
}
int main(){
    int n,k,i,j,x,y,ans,qw=0;
    scanf("%d%d",&n,&k);
    for(i=0;i<n-1;i++){
        scanf("%d%d",&x,&y);
        s[x].push_back(y);
        s[y].push_back(x);
    }
    ans=2*(n-1);
    vi[1]=1,dfs(1,0),vi[1]=0;
    x=p,vi[p]=1,dfs(p,0),vi[x]=0;
    flag=1,x=p,vi[p]=1,dfs(p,0),vi[x]=0;
    arr.clear();
    ans-=tmp-1;
    if(k==1){
        printf("%d\n",ans);
    }
    else{
        memset(vi,0,sizeof(vi));
        for(i=0;i<que.size();i++)
            vi[que[i]]=1;
        for(i=0;i<que.size();i++){
            tmp=0;
            p=que[i];
            dfs(p,0);
            arr.push_back(tmp);
            vi[que[i]]=0,vi[p]=1;
            dfs(p,0);
            vi[que[i]]=1;
            qw=max(qw,tmp);
        }
        for(i=0;i<que.size();i++){
            for(j=i+1;j<que.size();j++)
                qw=max(qw,arr[i]+arr[j]-(j-i));
        }ans-=qw-1;
        printf("%d\n",ans);
    }
}