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);
        }
    }
}

补充：软件开发 , C++ ,

上一个：HDU 2196 Computer - from lanshui_Yang
下一个：hdu 4608 暴力大数