Description：

$n$ 个村庄呈树形结构，警察从 $1$ 出发遍历所有村庄，修建 $k$ 条路，建好后每条路必须经过一次，求修完后的最小距离。

$1\le n \le 10^5,1\le k \le 2$

Solution：

$k$ 只有 $1$ 或 $2$ 两种情况，对于 $k=1$ 的情况，原图中每条路会被走两次，而建一条路后这条路连接的两个点在原图中的路径只会被走一次，所以只要求树的直径用原来边数 $\times2$ 减掉再加一即可。

对于 $k=2$ 的情况，如果新形成的环没有在原来直径上，那么不变，如果在了，因为建好后每条路至少走一次，会发现原来只用走一次的现在还要走两次，于是边权应为 $-1$ ，再用 $DP$ 求直径即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,t;

#define MAXN 100010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b)

{

	e[edgenum].to = b;e[edgenum].v = 1;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].v = 1;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int d[MAXN];

bool v[MAXN];

int pre[MAXN];

void bfs(int s)

{

	d[s] = 0;

	queue<int> q;

	q.push(s);

	memset(v,0,sizeof(v));

	memset(d,0,sizeof(d));

	v[s] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(!v[e[i].to])

			{

				pre[e[i].to] = i;

				d[e[i].to] = d[k] + e[i].v;

				q.push(e[i].to);

				v[e[i].to] = true;

			}

		}

	}

	return;

}

int f[MAXN],res = -1;

void dp(int k)

{

	v[k] = true;

	int g = 0;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			dp(e[i].to);

			res = max(res,g + f[e[i].to] + e[i].v);

			g = max(g,f[e[i].to] + e[i].v);

			f[k] = max(f[k],f[e[i].to] + e[i].v);

		}

	}

	return;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&t);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	bfs(1);

	int st,en,maxd = -1;

	for(int i = 1;i <= n;++i)

	{

		if(d[i] > maxd)

		{

			maxd = d[i];

			st = i;

		}

	}

	bfs(st);

	maxd = -1;

	for(int i = 1;i <= n;++i)

	{

		if(d[i] > maxd)

		{

			maxd = d[i];

			en = i;

		}

	}

	if(t == 1)

	{

		cout << (n - 1) * 2 - maxd + 1 << endl;

		return 0;

	}

	for(int i = en;i != st;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].v = -1;

		e[pre[i] ^ 1].v = -1;

	}

	int ans = (n - 1) * 2 - maxd + 1;

	memset(v,0,sizeof(v));

	dp(1);

	if(res > 1)cout << ans - res + 1 << endl;

	else cout << ans << endl;

	return 0;

}