/* bfs+求树的直径 关键：if k<=maxs+1 直接输出k-1； else： k肯定的是包括最长路。先从最长路的起点出发，再走分支，最后到达最长路的终点。 因此是2*(k-(maxs+1))+maxs; */ #include #include #include #include #include #include #include #include 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 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; }