题意：n个点的树，给出n-1条边，每条边长都是1，，两个点建立防火站，使得其他点到防火站的最远距离最短。
思路：先求出树的直径，直径上的所有点都存到一个数组里。如果直径是奇数，把中间的那条边删去；如果是偶数，把中间的点，分
到两边的子树。对两个子树分别求树直径的中点即可。详见代码：
/********************************************************* file name: zoj3820.cpp author : kereo create time: 2015年02月08日 星期日 15时31分32秒*********************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>#include<map>#include<vector>#include<stack>#include<cmath>#include<string>#include<algorithm>using namespace std;typedef long long ll;const int sigma_size=26;const int N=100+50;const int MAXN=200000+50;const int inf=0x3fffffff;const double eps=1e-8;const int mod=1000000000+7;#define L(x) (x<<1)#define R(x) (x<<1|1)#define PII pair<int, int>#define mk(x,y) make_pair((x),(y))int n,edge_cnt,top;int head[MAXN],vis[MAXN],d[MAXN],fa[MAXN],s[MAXN];struct Edge{int v,next;}edge[MAXN<<1];void init(){edge_cnt=0;memset(head,-1,sizeof(head));}void addedge(int u,int v){edge[edge_cnt].v=v;edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;}int bfs(int st){int ans=st;queue<int>Q; Q.push(st);vis[st]=1; d[st]=0; fa[st]=-1;while(!Q.empty()){int u=Q.front(); Q.pop();for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(vis[v])continue;vis[v]=1; d[v]=d[u]+1; fa[v]=u;if(d[v]>d[ans])ans=v;Q.push(v);}}top=0;int u=ans;while(u!=-1){s[top++]=u; u=fa[u];}return ans;}int main(){//freopen("in.txt","r",stdin);int T;scanf("%d",&T);while(T–){init();scanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v); addedge(v,u);}for(int i=1;i<=n;i++)vis[i]=0;int st=bfs(1);for(int i=1;i<=n;i++)vis[i]=0;int ed=bfs(st);int depth=d[ed]+1;int l=s[depth/2-1],r=s[depth/2];//printf("st=%d ed=%d depth=%d l=%d r=%d\n",st,ed,depth,l,r);int cnt=edge_cnt;init();for(int i=0;i<cnt;i++){if((edge[i^1].v == l && edge[i].v == r) || (edge[i^1].v == r && edge[i].v == l))continue;addedge(edge[i^1].v,edge[i].v);}int sp1=s[depth/2],sp2=s[(depth-1)/2];int v[MAXN];for(int i=1;i<=n;i++)vis[i]=0;st=bfs(sp1);for(int i=0;i<=n;i++)v[i]=vis[i];for(int i=1;i<=n;i++)vis[i]=0;ed=bfs(st);int dep=d[ed]+1;int ans1=s[dep/2],dep1=dep;if(depth & 1){addedge(l,r); addedge(r,l);v[sp1]=0;}elsesp1=sp2;for(int i=0;i<=n;i++)vis[i]=v[i];st=bfs(sp1);for(int i=1;i<=n;i++)vis[i]=v[i];ed=bfs(st);dep=d[ed]+1;int dep2=dep,ans2=s[dep/2];/*if(dep & 1)ans2=s[dep/2];elseans2=s[(dep-1)/2];*///printf("ans1=%d ans2=%d dep1=%d dep2=%d\n",ans1,ans2,dep1,dep2);if(ans1 == ans2)printf("%d %d %d\n",depth/2,ans1,ans1 == 1? 2 : 1);elseprintf("%d %d %d\n",max(dep1/2,dep2/2),ans1,ans2);}return 0;}
会得到最大的满足，因为它填补了你的空虚。
