树的直径。。。。

Park Visit

1
4 2
3 2
1 2
4 2
2
4

1
4

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

using namespace std;

const int maxn=150100;

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

int n,Q,Adj[maxn],Size;
int dist[maxn];
bool vis[maxn];

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

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

int get_diameter()
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(dist,0,sizeof(dist));
    q.push(1); vis[1]=true;
    while(!q.empty())
    {
        int v,u=q.front(); q.pop();
        for(int i=Adj[u];~i;i=edge[i].next)
        {
            v=edge[i].to;
            if(vis[v]) continue;
            vis[v]=1;dist[v]=dist[u]+1;
            q.push(v);
        }
    }
    int goal=-1,mark=-1;
    for(int i=1;i<=n;i++)
    {
        if(dist[i]>mark)
        {
            mark=dist[i];
            goal=i;
        }
    }

    memset(vis,0,sizeof(vis));
    memset(dist,0,sizeof(dist));
    q.push(goal); vis[goal]=true;
    while(!q.empty())
    {
        int v,u=q.front(); q.pop();
        for(int i=Adj[u];~i;i=edge[i].next)
        {
            v=edge[i].to;
            if(vis[v]) continue;
            vis[v]=1; dist[v]=dist[u]+1;
            q.push(v);
        }
    }

    goal=-1;
    for(int i=1;i<=n;i++) goal=max(goal,dist[i]);

    return goal;
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
while(T_T--)
{
    scanf("%d%d",&n,&Q);
    init();
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        Add_Edge(u,v);
        Add_Edge(v,u);
    }
    int dia=get_diameter();
    while(Q--)
    {
        int x;
        scanf("%d",&x);
        x--;
        if(x<=dia) printf("%d\n",x);
        else printf("%d\n",dia+(x-dia)*2);
    }
}
    return 0;
}

HDOJ 4607 Park Visit,布布扣,bubuko.com

HDOJ 4607 Park Visit

原文：http://blog.csdn.net/u012797220/article/details/22426179