hdu 4607 Park Visit

http://acm.hdu.edu.cn/showproblem.php?pid=4607
まず木の直径の方法を求めます:2回bfs、任意の1点a a点の最も遠い点bを求めて、それからb点の最も遠い点cを求めます
このようにbとcの間の経路は木の直径である
そして討論
直径上の点個数をkとする   アクセスするポイント数v
1)v<=kなら直接直径で見学できる  パスはv-1
2)v>kはまず直径を歩かなければならないがm=v-k  このmポイントは他の枝葉にアクセスするのに2*mかかります
コード:

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<cmath>

#include<set>

#include<map>

#include<stack>

#include<vector>

#include<algorithm>

#include<queue>

#include<stdexcept>

#include<bitset>

#include<cassert>

#include<deque>

#include<numeric>



using namespace std;



typedef long long ll;

typedef unsigned int uint;

const double eps=1e-12;

const int INF=0x3f3f3f3f;

const ll MOD=1000000007;

const int N=200005;

int head[N],I;

struct node

{

    int j,next;

}edge[N];

int dist[N];

void add(int i,int j)

{

    edge[I].j=j;

    edge[I].next=head[i];

    head[i]=I++;

}

int bfs(int x1,int n)

{

    queue<int>qt;

    memset(dist,-1,sizeof(dist));

    dist[x1]=0;

    qt.push(x1);

    while(!qt.empty())

    {

        int x=qt.front();

        qt.pop();

        for(int t=head[x];t!=-1;t=edge[t].next)

        {

            int j=edge[t].j;

            if(dist[j]==-1)

            {

                dist[j]=dist[x]+1;

                qt.push(j);

            }

        }

    }

    int k=x1;

    for(int i=1;i<=n;++i)

    if(dist[i]>dist[k])

    k=i;

    return k;

}

int main()

{

    //freopen("data.in","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

        scanf("%d %d",&n,&m);

        memset(head,-1,sizeof(head));I=0;

        for(int i=1;i<n;++i)

        {

            int l,r;

            scanf("%d %d",&l,&r);

            add(l,r);

            add(r,l);

        }

        int k=bfs(1,n);

        k=bfs(k,n);

        k=dist[k]+1;

        while(m--)

        {

            int a;

            scanf("%d",&a);

            if(a<=k)

            printf("%d
",a-1);

            else

            printf("%d
",k-1+2*(a-k));

        }

    }

    return 0;

}