C++14(g++5.4) 解法, 执行用时: 327ms, 内存消耗: 22184K, 提交时间: 2020-06-14 14:53:09

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 2e5 + 111;
vector<int>G[maxn];
void add(int x, int y) {
	G[x].push_back(y);
}
int f[maxn];
int dep[maxn];
int dfs(int x, int fa, int d) {
	dep[x] = d;
	f[x] = fa;
	for (int p : G[x]) {
		if (p == fa) continue;
		dfs(p, x, d + 1);
	}
	return 0;
}

int de[maxn];
int ans = 0;


int dfs1(int x, int fa, int d) {
	ans = max(d, ans);
	for (int p : G[x]) {
		if (p == f[x]) continue;
		dfs1(p, x, d + 1);
	}
	return 0;
}

int main() {
	int n, k;
	cin >> n >> k;
	if (n == 1) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	dfs(1, -1, 0);
	int a = k;

	int len = (dep[k] - 1) / 2;
	for (int i = 0; i < len; i++) k = f[k];

	int root = k;

	dfs1(root, f[root], 0);
	ans++;
	ans += len;
	if (dep[a] % 2 == 0) {
		ans++;
	}
	
	cout << 2*ans << endl;
	return 0;
}
/*
10 5
1 2
2 3
3 4
4 5
4 6
6 7
3 8
8 9
9 10


*/

C++11(clang++ 3.9) 解法, 执行用时: 304ms, 内存消耗: 21456K, 提交时间: 2020-07-05 11:35:47

#include <bits/stdc++.h>
using namespace std;
#define N 202020
vector<int> v[N];
int n, x, dep[N], ans;
void go(int now, int prt, int ndep) {
	dep[now] = ndep;
	for (int son : v[now]) {
		if (son == prt) continue;
		go(son, now, ndep + 1);
	}
}
int bdr;
void go2(int now, int prt) {
	if (dep[now] <= bdr) return;
	ans = max(ans, dep[now]);
	for (int son : v[now]) {
		if (son == prt) continue;
		go2(son, now);
	}
}
int main() {
	cin >> n >> x;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	go(1, 1, 0);
	bdr = dep[x] / 2;
	go2(x, x);
	printf("%d\n", ans << 1);
}