题目来源的原文是 2014 ACM-ICPC Asia Mudanjiang Regional Contest, 大概就叫这个名字了。

这题考察了对树直径的性质的理解和运用，有 $\mathcal O(n \log_2 n)$ 的二分做法，但是巧妙运用性质就可以做到线性。

在树上标记两个点，使树上点到最近的标记点的距离最大的最小

看到最大值最小，很快想到二分，二分确实也可以做，但这有一种奇妙的做法可以让它变成线性。

在讲树的直径的时候肯定已经证明过，树上离一个点距离最远的点一定是直径的一个端点，由这个性质我们很容易可以得到直径旁边伸出去的枝节一定没有直径深，所以如果标记的点在那些枝节上，把它靠近直径移动不会使它离它的最长点变长，而会使它到直径端点的距离变短，所以标记一定在树的直径上。

有了这个结论，只要把直径劈成两半，然后在两边求中心就可以了。仔细想想为什么，还是很妙的。

注意是中心，不是重心。

求中心的方法可以借鉴我 CodeChef 一道题的题解。至于劈开树，只需要在 dfs 开始的时候把父亲设为不能去的隔壁那个就可以了。

代码。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
const int N = 200005, F = 1, INF = 0x3f3f3f3f;
int TWT, n, x, y, S, T, ans, ansu1, ansu2, anss, dep[N], size[N], pre[N], up[N], down[N], maxL;
std::vector<int> g[N], d;
void init() {
	for(int i = 0; i < N; i++) g[i].clear();
	memset(dep, 0, sizeof dep);
	d.clear();
}
void dfs(int u, int fa, int opt) {
	if(opt == F && dep[u] > dep[S]) S = u;
	else if(opt != F && dep[u] > dep[T]) T = u;
	for(int i = 0; i < (signed)g[u].size(); i++) {
		int v = g[u][i];
		if(v == fa) continue;
		dep[v] = dep[u] + 1;
		dfs(v, u, opt);
	}
}
void color(int u, int fa) {
	for(int i = 0; i < (signed)g[u].size(); i++) {
		int v = g[u][i];
		if(v == fa) continue;
		color(v, u);
		pre[v] = u;
	}
}
void getdown(int u, int fa) {
	for(int i = 0; i < (signed)g[u].size(); i++) {
		int v = g[u][i];
		if(v == fa) continue;
		getdown(v, u);
		down[u] = std::max(down[u], down[v] + 1);
	}
}
void getup(int u, int fa) {
	int max = -1, sax = -1;
	for(int i = 0; i < (signed)g[u].size(); i++) {
		int v = g[u][i];
		if(v == fa) continue;
		if(down[v] + 1 > max) sax = max, max = down[v] + 1;
		else if(down[v] + 1 > sax) sax = down[v] + 1;
	}
	for(int i = 0; i < (signed)g[u].size(); i++) {
		int v = g[u][i];
		if(v == fa) continue;
		up[v] = std::max(up[u] + 1, (max == down[v]+1) ? (sax+2) : (max+2));
		getup(v, u);
	}
}
void getans(int u, int fa, int &ans) {
	for(int i = 0; i < (signed)g[u].size(); i++) {
		int v = g[u][i];
		if(v == fa) continue;
		getans(v, u, ans);
	}
	int max = std::max(down[u], up[u]);
	if(max < maxL) maxL = max, ans = u;
}
void findCe(int u, int fa, int &ans) {
	maxL = 0x3f3f3f3f;
	memset(up, 0, sizeof up);
	memset(down, 0, sizeof down);
	getdown(u, fa);
	getup(u, fa);
	getans(u, fa, ans);
}
int main() {
	scanf("%d", &TWT);
	while(TWT--) {
		init();
		scanf("%d", &n);
		for(int i = 1; i < n; i++) {
			scanf("%d%d", &x, &y);
			g[x].push_back(y), g[y].push_back(x);
		}
		dfs(1, 0, F);
		memset(dep, 0, sizeof dep); 
		dfs(S, 0, !F);
		color(S, 0);
		for(int i = T; i != S; i = pre[i]) d.push_back(i);
		d.push_back(S);
		findCe(d[d.size() / 2], d[d.size()/2-1], ansu2);
		findCe(d[d.size() / 2 - 1], d[d.size()/2], ansu1);
		ans = std::max(dep[T] - dep[ansu1], 
		      std::max(dep[ansu2], 
		      std::max(dep[ansu1] - dep[d[d.size()/2-1]], 
		      		   dep[d[d.size()/2]] - dep[ansu2])));
		printf("%d %d %d", ans, ansu1, ansu2);
		if(TWT != 0) puts("");
	}
}