hdu 4607 Park Visit

兩次bfs求出最長鏈d，那麼解就有2種情況，如果k<=d+1,那直接輸出k-1，也就是在鏈上走，如果大於d+1,同樣也要走這條鏈，只不過中間要走一些分支來補充。

而走一個分支點消耗的距離是1*2（來回）。1Y

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define N 100005
int n,m;
vector<int> map[N];
bool vis[N];

int d;
struct node
{
    int pos;
    int dis;
}start,end;
node bfs(node k)
{
    memset(vis,0,sizeof(bool)*(n+5));
    queue<node> Q;
    Q.push(k);
    vis[k.pos]=1;
    node point,tmp;
    while(!Q.empty())
    {
        point=Q.front(); Q.pop();
        for(int i=0;i<map[point.pos].size();i++)
        {
            if(vis[map[point.pos][i]]) continue;
            tmp=point;
            tmp.pos=map[point.pos][i];
            tmp.dis=point.dis+1;
            vis[tmp.pos]=1;
            Q.push(tmp);
        }
    }
    d=point.dis;
    return point;
}
int main()
{
    int T,a,b;
    scanf("%d",&T);
    node k;
    int q;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) map[i].clear();

        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            map[b].push_back(a);
        }
        k.pos=1,k.dis=0;
        start=bfs(k);start.dis=0;
        end=bfs(start);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&q);
            if(q<=d+1) printf("%d\n",q-1);
            else printf("%d\n",d+(q-d-1)*2);
        }
    }
}