HDU4607+BFS

BFS求树的直径。

/*
bfs+求树的直径
关键：if k<=maxs+1 直接输出k-1；
	else： k肯定的是包括最长路。先从最长路的起点出发，再走分支，最后到达最长路的终点。
			因此是2*(k-(maxs+1))+maxs;
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<math.h>
using namespace std;
typedef long long ll;
//typedef __int64 int64;
const int maxn = 100005;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
struct Node{
	int v,next;
}edge[ maxn<<1 ];
int cnt,head[ maxn ];
int vis[ maxn ],dis[ maxn ];
int maxs,maxNode;
void init(){
	cnt = 0;
	memset( head,-1,sizeof( head ) );
}
void addedge( int a,int b ){
	edge[ cnt ].v = b;
	edge[ cnt ].next = head[ a ];
	head[ a ] = cnt++;
	
	edge[ cnt ].v = a;
	edge[ cnt ].next = head[ b ];
	head[ b ] = cnt++;
}
void bfs( int s,int n ){
	memset( vis,0,sizeof( vis ) );
	vis[ s ] = 1;
	queue<int>q;
	q.push( s );
	//for( int i=0;i<=n;i++ )
		//dis[ i ] = inf;
	dis[ s ] = 0;
	maxs = 0;
	while( !q.empty() ){
		int cur = q.front();
		q.pop();
		if( dis[ cur ]>maxs ){
			maxs = dis[ cur ];
			maxNode = cur;
		}
		//maxs = max( maxs,dis[ cur ] );
		for( int i=head[ cur ];i!=-1;i=edge[ i ].next ){
			int v = edge[ i ].v;
			if( vis[ v ]==1 ) continue;
			vis[ v ] = 1;
			dis[ v ] = dis[ cur ]+1;
			q.push( v );
		}	
	}
	return ;
}
int main(){
	int T;
	scanf("%d",&T);
	while( T-- ){
		int n,m;
		scanf("%d%d",&n,&m);
		int a,b;
		init();
		int N = n-1;
		while( N-- ){
			scanf("%d%d",&a,&b);
			addedge( a,b );
		}
		bfs( 1,n );
		bfs( maxNode,n );
		//maxs=the R of the tree
		while( m-- ){
			scanf("%d",&b);
			if( b<=maxs+1 ) printf("%d\n",b-1);
			else printf("%d\n",2*(b-maxs-1)+maxs);
		}
	}
	return 0;
}