题意：n个点的树，给出n-1条边，每条边长都是1，两个点建立防火站，使得其他点到防火站的最远距离最短。
思路：比赛的时候和队友一开始想是把这两个点拎起来，使得层数最少，有点像是树的中心，于是就猜测是将树的中心找到后，将两棵左右子树分别求树的中心，这两棵树的中心就是答案，but另外一个队友又说了个反例，脑子也不清醒，以为还有没考虑到的，比赛也没A，赛后一想就是最初的猜想，回来之后写了写，报栈了，数据范围太大，真不想改，今天改了改，改成bfs又tle了，囧囧的，把memset和memcpy都改成循环AC了，代码写的很不优雅。
如果最一开始树的直径是偶数，即1-2-3-4，则拆成1-2和3-4。
如果最一开始树的直径是奇数，即1-2-3-4-5，则拆成1-2-3和3-4-5。
丑丑的代码：
/*===============================================================
* Copyright (C) 2014 All rights reserved.
*
* File Name: zoj3172.cpp
* Author:sunshine
* Created Time: 2014年10月14日
*
================================================================*/
#include <map>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm> using namespace std; #define N 500010 int head[N];
int edgeNum;
struct Edge{
int v,to;
}edge[N];
int edge_u_v[N][]; void addedge(int a,int b){
edge[edgeNum].v = b;
edge[edgeNum].to = head[a];
head[a] = edgeNum ++;
} int vis[N],depth,ind;
int t_vis[N],father[N];
int stack[N];
void bfs(int u){
vis[u] = ;
queue<int>que;
que.push(u);
while(!que.empty()){
int tmp = que.front();
que.pop();
if(vis[tmp] >= depth){
depth = vis[tmp];
ind = tmp;
}
for(int i = head[tmp];i != -;i = edge[i].to){
int v = edge[i].v;
if(vis[v] == ){
vis[v] = vis[tmp] + ;
father[v] = tmp;
que.push(v);
}
}
}
int tmp = ind;
for(int i = ;i < depth;i ++){
stack[i] = tmp;
tmp = father[tmp];
}
return ;
} void init(int n){
edgeNum = ;
//memset(head,-1,sizeof(head));
//memset(vis,0,sizeof(vis));
//memset(father,-1,sizeof(father));
for(int i = ;i <= n;i ++) {
head[i] = -;
vis[i] = ;
father[i] = -;
}
} int main(){
int t;
int n;
int u,v;
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
scanf("%d",&t);
while(t --){
scanf("%d",&n); init(n);
for(int i = ;i < n - ;i ++){
scanf("%d%d",&u,&v);
edge_u_v[i][] = u;
edge_u_v[i][] = v;
addedge(u,v);
addedge(v,u);
} depth = ;
bfs();
for(int i = ;i <= n;i ++) vis[i] = ;
bfs(ind); int ans_one,ans_two;
int depth_one,depth_two;
//left graph
init(n);
u = stack[depth / - ];//chai bian
v = stack[depth / ];
for(int i = ;i < n - ;i ++){
if((edge_u_v[i][] == u && edge_u_v[i][] == v)
|| (edge_u_v[i][] == u && edge_u_v[i][] == v)) ;
else{
addedge(edge_u_v[i][],edge_u_v[i][]);
addedge(edge_u_v[i][],edge_u_v[i][]);
}
} int seperation = stack[depth / ];//the seperation of left and right
int seperation1 = stack[(depth - ) / ];
int long_depth = depth;
depth = ;
bfs(seperation);
for(int i = ;i <= n;i ++) t_vis[i] = vis[i];
for(int i = ;i <= n;i ++) vis[i] = ;
bfs(ind);
ans_one = stack[depth/];//if depth&1 mid else right
depth_one = depth; if(long_depth&){
addedge(u,v);
addedge(v,u);
t_vis[seperation] = ;
}else{
seperation = seperation1;
}
depth = ;
for(int i = ;i <= n;i ++) vis[i] = t_vis[i];
bfs(seperation);
for(int i = ;i <= n;i ++) vis[i] = t_vis[i];
bfs(ind);
if(depth & ) ans_two = stack[depth/];
else ans_two = stack[(depth-)/];
depth_two = depth; if(ans_one == ans_two){
printf("%d %d %d\n",long_depth/,ans_one,(ans_one == )?:);
}else{
printf("%d %d %d\n",max(depth_one/,depth_two/),ans_one,ans_two);
} }
return ;
}