题目描述

Description

Input

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

Output

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

Sample Input

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

Sample Output

11

HINT

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

题目分析

当k=1 明显选择一条直径的两个端点来修建道路
这时形成了一个环
当k=2时
假设建的第二条道路形成的环与第一个环没有重叠 那么和第一问的计算方式一样
假设建的第二条道路形成的环与第一个环有重叠 那么只能多经过一次重叠部分 才能经过修建的第二条道路 相当于重叠部分对最终答案没有贡献
那么 我们把第一次选出的直径上的边权设为-1 再求一遍直径即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
int tot=1;
int head[100100],net[200200],to[200200],val[200200];
void add(int x,int y,int c)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c;
}
int s1[100100],s2[100100];
int num,ans;
int dfs(int x,int temp)
{
    int mx1=0,mx2=0;
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==temp) continue;
        int tmp=val[i]+dfs(to[i],x);
        if(tmp>mx1) mx2=mx1,mx1=tmp,s2[x]=s1[x],s1[x]=i;
        else if(tmp>mx2) mx2=tmp,s2[x]=i;
    }
    if(mx1+mx2>ans) ans=(mx1+mx2),num=x;
    return mx1;
}
int main()
{   
    scanf("%d%d",&n,&k);
    for(int x,y,i=1;i<n;i++) 
        scanf("%d%d",&x,&y),add(x,y,1),add(y,x,1);
    dfs(1,0);
    if(k==1) printf("%d",2*(n-1)-ans+1);
    else
    {
        for(int i=s1[num];i;i=s1[to[i]]) val[i]=-1,val[i^1]=-1;
        for(int i=s2[num];i;i=s1[to[i]]) val[i]=-1,val[i^1]=-1;
        int sum=2*(n-1)-ans+1;
        ans=0;
        dfs(1,0);
        sum=sum-ans+1;
        printf("%d",sum);
    }
    return 0;
}