Hdu 4607 Park Visit 2013多校1 (树的直径)

Dear 丶 2022-08-27 03:55 143阅读 0赞

题意：一个连通图，有N个点和N-1条边，由边数可知图中无环。每条边长度都为1,问要到达图中任意k个点的最短路径，其中起点可以从k个顶点中任意一个出发。

思路：首先如果k小于等于直径长度+1（也就是在直径上的点数），那么答案为k−1;

如果k大于直径长度+1，设直径长度为len，那么答案为len+(k−len-1)\*2;

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=200005;
    
    struct Node
    {
    	int v,w;
    	int next;
    }edges[N];
    
    int n,m,e,maxlenth;
    int head[N],dis[N];
    bool vis[N];
    int point_u;
    
    void Add (int u,int v,int w)
    {
    	edges[e].v=v;
    	edges[e].w=w;
    	edges[e].next=head[u];
    	head[u]=e++;
    }
    
    int BFS (int u)
    {
    	memset(vis,false,sizeof(vis));
    	memset(dis,0,sizeof(dis));
    	queue<int> Q;
    	Q.push(u);
    	vis[u] = true;
    	while (!Q.empty())
    	{
    		int s=Q.front();
    		Q.pop();
    		for (int i=head[s];i!=-1;i=edges[i].next)
    		{
    			int v=edges[i].v;
    			if (vis[v]==false)
    			{
    				dis[v]=dis[s]+edges[i].w;
    				Q.push(v);
    				vis[v]=true;
    				if (dis[v]>maxlenth)
    				{
    					maxlenth=dis[v];
    					point_u=v;
    				}
    			}
    		}
    	}
    	return maxlenth;
    }
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        while (T--)
    	{
    	    scanf("%d%d",&n,&m);
    		memset(head,-1,sizeof(head));
    		int u,v,i;
    		maxlenth=0;
    		e=0;
    		for (i=1;i<n;i++)
    		{
    			scanf("%d%d",&u,&v);
    			Add(u,v,1);
    			Add(v,u,1);
    		}
    		BFS(1);
    		BFS(point_u);
    		for (i=0;i<m;i++)
    		{
    		    scanf("%d",&u);
    		    if(u<=maxlenth+1)
                    printf("%d\n",u-1);
                else
                printf("%d\n",maxlenth+2*(u-maxlenth-1));
    		}
    	}
    	return 0;
    }