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
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。
Source
一道画画图就能搞出来的题。。。
首先我们应该想想他让我们修路有什么用。你随便画一棵树就很容易发现，要想从一个点出发经过所有点一遍再回来，每条边是要经过两次的。而我们修路就是为了让其中一些边只走一次。
K=1：显然我们随意连一条边会形成一个环，环上的边我们只用经过一次。这样我们最大化环的的长度就行，也就是找到树的直径。
K=2：首先我们肯定还是连直径。但是第二条边怎么连？显然我们还可以找次长链出来。但如果两条链有重叠怎么办？
我们可以把第一条链在算完长度后将所有边权赋成-1，这样就不会算重了。设两次选的边长度分别为l1,l2，那么答案就是2*n-l1-l2.。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct point
{
int to;
int next;
int dis;
}e[];
int n,k,x,y,l1,l2,num,maxn,s,t;
int pre[],head[],d[],pr[];
bool vis[];
void add(int from,int to,int dis)
{
e[++num].next=head[from];
e[num].to=to;
e[num].dis=dis;
head[from]=num;
}
void dfs1(int x)
{
vis[x]=true;
for(int i=head[x];i!=;i=e[i].next)
{
int to=e[i].to;
if(!vis[to])
{
d[to]=d[x]+e[i].dis;
dfs1(to);
}
}
}
void dfs2(int x)
{
vis[x]=true;
for(int i=head[x];i!=;i=e[i].next)
{
int to=e[i].to;
if(!vis[to])
{
d[to]=d[x]+e[i].dis;
pre[to]=x;
dfs2(to);
}
}
}
void dp(int x)
{
vis[x]=true;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(!vis[to])
{
dp(to);
l2=max(l2,d[to]+d[x]+e[i].dis);
d[x]=max(d[x],d[to]+e[i].dis);
}
}
}
void change()
{
for(int i=t;i!=;i=pre[i])
pr[i]=pre[i];
for(int i=;i<=n;i++)
{
for(int j=head[i];j!=;j=e[j].next)
{
int to=e[j].to;
if(pr[i]==to||pr[to]==i)
e[j].dis=-;
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n-;i++)
{
scanf("%d%d",&x,&y);
add(x,y,);
add(y,x,);
}
dfs1();
for(int i=;i<=n;i++)
if(d[i]>maxn)
{
maxn=d[i];
s=i;
}
memset(vis,false,sizeof(vis));
memset(d,,sizeof(d));
dfs2(s);
for(int i=;i<=n;i++)
if(d[i]>l1)
{
l1=d[i];
t=i;
}
if(k==)
{
printf("%d",*(n-)+-l1);
return ;
}
change();
memset(d,,sizeof(d));
memset(vis,false,sizeof(vis));
dp();
printf("%d",*n-l1-l2);
return ;
}