ZOJ 3820 Buiilding Fire Stations 2分+BFS

サブ+BFS：
によるとhttp://blog.renren.com/blog/240107793/937020122 二つのガソリンスタンドは木の直径に違いない。
二分長L、bfsは直径の二つの端点を見つけて、直径端点Lまでのところにガソリンスタンドを建てて、bfsを検査します。
Buiding Fire Station
Time Limit: 5 Seconds     
メモリLimit: 131313072 KB     
Special Jundge
Marjar University is a beautiful and peaceful place.The re are N buildings and N - 1 bidirectional roads in the campus.The buildings are connected by roads in such a way that there is exactly one path between any tbuildings.By coincidence，the length of each road is 1 unit.
To ensure the campus security，Edward，the headmaster of Marjar University，plans to setup two fire stations in two different buildings so that firefighters arrive at the scene of the fire as so on as possible whenever fires occur.That means the longest distance bets and firtine
As a clever and diligent student in Marjar University，you are asked to write a program to compplete the plan.Please find out proper buildings to setup the fire stations.
Input
The re are multiple test cases.The first line of input contains an integer T indicating the number of test cases.For each test case:
The first line contains an integer N （2<= N <= 2000)
For the next N - 1ライン、each line contains two integers Xi and Yi.That means there is a road connecting building Xi and building Yi （indexes are 1-based）
Output
For each test case，output three integers.The first one is the minimal longest distance between a building and its neares fire station.The next two integers the indexs of the two buildings sectefied.fited
If there are multiple solutions，any one will be acceptable.
Sample Input

2
4
1 2
1 3
1 4
5
1 2
2 3
3 4
4 5

Sample Output

1 1 2
1 2 4

Author: 
YU，XiaoyaoZHUANG，Junyan
ソース: 
The 2014 ACM-ICPC Asia Mdanjiang Regional Conttest

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int maxn=200200;
const int INF=0x3f3f3f3f;

struct Edge
{
    int to,next;
}edge[maxn*2];

int Adj[maxn],Size;

void init()
{
    memset(Adj,-1,sizeof(Adj)); Size=0;
}

void addedge(int u,int v)
{
    edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++;
}

int n;
int dist[maxn],pre[maxn];

int bfs(int u)
{
    queue<int> q;
    q.push(u); dist[u]=0;  pre[u]=0;

    while(!q.empty())
    {
        u=q.front(); q.pop();
        for(int i=Adj[u];~i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dist[v]>dist[u]+1)
            {
                dist[v]=dist[u]+1;
                pre[v]=u;
                q.push(v);
            }
        }
    }

    return u;
}

bool check(int& s,int& e,int L)
{
    memset(dist,63,sizeof(dist));

    s=bfs(1);
    for(int i=0;i<L;i++)
    {
        s=pre[s];
        if(s==0)
        {
            e=s%n+1;
            return true;
        }
    }

    memset(dist,63,sizeof(dist));
    e=bfs(s);
    for(int i=0;i<L;i++)
    {
        e=pre[e];
        if(e==0)
            return true;
    }

    if(s==e) e=s%n+1;

    bfs(e);

    for(int i=1;i<=n;i++)
        if(dist[i]>L) return false;
    return true;
}

int nextInt()
{
    int ret=0;
    bool ok=false;
    char ch;
    while(ch=getchar())
    {
        if(ch>='0'&&ch<='9')
        {
            ret=ret*10+ch-'0';
            ok=true;
        }
        else if(ok==true) break;
    }
    return ret;
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        init();
        scanf("%d",&n);
        for(int i=0;i<n-1;i++)
        {
            int u,v;
            u=nextInt(); v=nextInt();
            addedge(u,v); addedge(v,u);
        }
        if(n==2)
        {
            printf("0 1 2
");
            continue;
        }
        else
        {
            int low=0,high=n,mid,ans;
            int s,e;
            while(low<=high)
            {
                mid=(low+high)/2;
                if(check(s,e,mid)==true)
                {
                    ans=mid;
                    high=mid-1;
                }
                else low=mid+1;
            }
            check(s,e,ans);
            printf("%d %d %d
",ans,s,e);
        }
    }
    return 0;
}