传送门：点击打开链接
题意：给你N个点，有N-1条边，构成了一棵树，每条边的距离都为1。现在要在N个点中选出2个点放灭火装置，要求N个点到最近的灭火装置的距离的最大值最小。求这两个点的位置。
思路：首先，一般让最大值最小，都是二分的方法。所以我们主要应该讨论，假如到灭火装置的距离最大值<=m时，是否能满足题意。选1为根节点，求出树的深度。对深度最大的那个点进行贪心策略。如果要使这个点被灭火装置覆盖，最优的方法应该是顺着边向根的方向移动m条边，或者已经到了根节点1了。那么在这个位置放一个灭火装置，最远的点肯定可以被覆盖，而且此时是能覆盖的点是最多的。然后我们从这个点出发将m条边能到达的点全部标记删除。重复上述步骤，在没有删除的点中找到深度最大的点，再向上找到放灭火装置的点，再删除一次点，最后统计是否n个点都被删除了，如果都被删除，说明m是可行的，否则m就是不可行的。
因为zoj是G++所以没办法扩栈，，所以只能全部用队列写了感觉不是很方便 。。
当然这题还要注意另外一些细节，因为灭火装置不能同时被安放在同一点，所以在第一个灭火装置放下后已经能覆盖所有的点时，第二个灭火装置再随便找个点即可。
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 200000 + 5;
const int ME = 400000 + 5;int Head[MX], Next[ME], rear;
struct Edge {int u, v;
} E[ME];
void edge_init() {rear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v) {E[rear].u = u;E[rear].v = v;Next[rear] = Head[u];Head[u] = rear++;
}bool vis[MX];
int ga, gb, gans;
int F[MX], dep[MX];struct Data {int u, f, d;Data(int _u, int _f, int _d) {u = _u; f = _f; d = _d;}
};void build() {queue<PII>Q;Q.push(PII(1, 0));F[1] = -1; dep[1] = 0;while(!Q.empty()) {PII f = Q.front();Q.pop();int u = f.first, d = f.second;for(int i = Head[u]; ~i; i = Next[i]) {int v = E[i].v;if(v == F[u]) continue;F[v] = u; dep[v] = d + 1;Q.push(PII(v, d + 1));}}
}int deal(int u, int x) {int ret = 0;queue<Data>Q;Q.push(Data(u, -1, x));while(!Q.empty()) {Data t = Q.front();Q.pop();int u = t.u, f = t.f, d = t.d;if(!vis[u]) ret += ++vis[u];if(d) for(int i = Head[u]; ~i; i = Next[i]) {int v = E[i].v;if(v == f) continue;Q.push(Data(v, u, d - 1));}}return ret;
}bool check(int n, int x) {memset(vis, 0, sizeof(vis));int u = 1, cnt = 0;for(int i = 2; i <= n; i++) {if(dep[i] > dep[u]) u = i;}for(int i = x; i >= 1 && F[u] != -1; i--, u = F[u]);ga = u;cnt += deal(u, x);if(cnt == n) {if(ga == 1) gb = 2;else gb = 1;return true;}u = -1;for(int i = 1; i <= n; i++) {if(!vis[i] && (u == -1 || dep[i] > dep[u])) u = i;}for(int i = x; i >= 1 && F[u] != -1; i--, u = F[u]);gb = u;cnt += deal(u, x);return cnt == n;
}int main() {int T, n; //FIN;scanf("%d", &T);while(T--) {edge_init();scanf("%d", &n);for(int i = 1; i <= n - 1; i++) {int u, v;scanf("%d%d", &u, &v);edge_add(u, v);edge_add(v, u);}build();int ma, mb, mans;int L = 0, R = n, m;while(L <= R) {m = (L + R) >> 1;if(check(n, m)) {ma = ga;mb = gb;mans = m;R = m - 1;} else L = m + 1;}printf("%d %d %d\n", mans, ma, mb);}return 0;
}