记录编号	576988	评测结果	WAWAWAAWWAWWWAAAAWAWWWWAWWWWWW
题目名称	[APIO 2010]巡逻	最终得分	36
用户昵称	该账号已注销	是否通过	未通过
代码语言	C++	运行时间	0.893 s
提交时间	2022-10-19 21:03:06	内存使用	43.51 MiB

#include <bits/stdc++.h>
using namespace std;

struct eg {
	int t, n, w;
} e[4001000];
int hd[2001000], cnt = 0, n, k, l1, l2, l;
bool qf = 0;

bool v[2001000] = {0};
int dis[2001000] = {0};
void add(int x, int y) {
	e[++cnt].t = y;
	e[cnt].n = hd[x];
	e[cnt].w = 1;
	hd[x] = cnt;
}

int bfs(int s) {
	queue<int>q;
	q.push(s);
	memset(v, 0, sizeof(v));
	memset(dis, 0, sizeof(dis));
	v[s] = 1;
	while (!q.empty()) {
		int u = q.front();

		q.pop();
		for (int i = hd[u]; i; i = e[i].n) {
			int ver = e[i].t;
			if (v[ver] == 1)
				continue;
			dis[ver] = dis[u] + e[i].w;
			q.push(ver);
			v[ver] = 1;
		}
	}
	int p, mx = 0;
	for (int i = 1; i <= n; i++) {
		if (dis[i] > mx) {
			mx = dis[i];
			p = i;
		}
	}
	l = dis[p];
	return p;
}

void dfs(int x, int fa, int y) {
	for (int i = hd[x]; i; i = e[i].n) {
		int ver = e[i].t;
		if (ver == fa)
			continue;
		if (ver == y) {
			qf = 1;
			e[i].w = -1;
			return ;
		}
		dfs(ver, x, y);
		if (qf == 1) {
			e[i].w = -1;
			return ;
		}
	}
}

int main() {
	freopen("xunluo.in", "r", stdin);
	freopen("xunluo.out", "w", stdout);
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}

	int st = bfs(1);
	int ed = bfs(st);
	l1 = l;
	if (k == 1) {

		cout << 2 * (n - 1) - (l1 - 1) << endl;
		return 0;
	}
	dfs(st, st, ed);
	st = bfs(1);
	ed = bfs(st);
	l2 = l;
	cout << 2 * (n - 1) - (l1 - 1) - (l2 - 1) << endl;
	return 0;
}