题意： 一棵树中，选取两点，使得(其他点到这两点的距离的最小值)的最大值最小
思路： 考虑只选取一点的情况，那么显然选取直径的中点即为答案。 首先考虑选取的两点肯定在直径上，因为假如不在直径上，那么把点往直径上移动，不会使得答案变得更劣。 再考虑选取两点，假如我们将树按照树的直径的中点分成两段，那么肯定是一边放一点。 因为假如两个点都在一边的话，答案肯定是\(\frac{len}{2}\)，\(len\)为树的直径长度。 那么既然两个点分别在两边的话，那显然是两边分别求个树的直径，再取中点放是最优的吧。
#include <bits/stdc++.h> using namespace std; #define N 200010 int n; vector <int> G[N]; int fa[N], dep[N], far; int get_far(int st) { queue <int> q; q.push(st); dep[st] = 1; fa[st] = -1; while (!q.empty()) { int u = q.front(); q.pop(); far = u; for (auto v : G[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; q.push(v); } } } void get_center(int st) { get_far(st); get_far(far); int shift = dep[far] / 2; if (dep[far] % 2 == 0) --shift; while (shift--) far = fa[far]; } int main() { int T; cin >> T; while (T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) G[i].clear(); for (int i = 1, u, v; i < n; ++i) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } get_center(1); int center = far; for (vector <int> ::iterator it = G[center].begin(); it != G[center].end(); ++it) if (*it == fa[center]) { G[center].erase(it); break; } for (vector <int> :: iterator it = G[fa[center]].begin(); it != G[fa[center]].end(); ++it) if (*it == center) { G[fa[center]].erase(it); break; } int p1, p2, dis; get_center(fa[center]); p1 = far; dis = dep[p1]; get_center(center); p2 = far; dis = max(dis, dep[p2]) - 1; printf("%d %d %d\n", dis, p1, p2); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/10666610.html
相关资源：JAVA上百实例源码以及开源项目