Problem Description

Claire and her little friend, ykwd, are travelling in Shevchenko's Park! The park is beautiful - but large, indeed. N feature spots in the park are connected by exactly (N-1) undirected paths, and Claire is too tired to visit all of them. After consideration, she decides to visit only K spots among them. She takes out a map of the park, and luckily, finds that there're entrances at each feature spot! Claire wants to choose an entrance, and find a way of visit to minimize the distance she has to walk. For convenience, we can assume the length of all paths are 1.
Claire is too tired. Can you help her?

 

Input

An integer T(T≤20) will exist in the first line of input, indicating the number of test cases.
Each test case begins with two integers N and M(1≤N,M≤10⁵), which respectively denotes the number of nodes and queries.
The following (N-1) lines, each with a pair of integers (u,v), describe the tree edges.
The following M lines, each with an integer K(1≤K≤N), describe the queries.
The nodes are labeled from 1 to N.

 

Output

For each query, output the minimum walking distance, one per line.

 

Sample Input

 

Sample Output

 

Source

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<bitset>

 #include<cassert>

 #include<cctype>

 #include<cmath>

 #include<cstdlib>

 #include<ctime>

 #include<deque>

 #include<iomanip>

 #include<list>

 #include<map>

 #include<queue>

 #include<set>

 #include<stack>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef long double ld;

 typedef pair<int,int> pii;

 const double PI=acos(-1.0);

 const double eps=1e-;

 const ll mod=1e9+;

 const int inf=0x3f3f3f3f;

 const int maxn=1e5+;

 const int maxm=+;

 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

 int n,m,cnt;//cnt为边数

 int dist[maxn],head[maxn];//dist表示最长路，head为存图用的

 bool vis[maxn];

 struct node{//定义边的结构体

     int from,to,val,next;

 }edge[maxn<<];//注意是无向图，边数是二倍的

 void init()//初始化，不可少

 {

     cnt=;

     memset(head,-,sizeof(head));

 }

 void addedge(int u,int v,int w)

 {

     edge[cnt].from=u;//起点

     edge[cnt].to=v;//终点

     edge[cnt].val=w;//权值

     edge[cnt].next=head[u];//指向下一条边

     head[u]=cnt++;

 }

 int length;//最终的最长路径(树的直径)

 int node;//记录端点值

 void bfs(int s)

 {

     queue<int>q;//定义队列

     memset(vis,false,sizeof(vis));//初始化，清零

     memset(dist,,sizeof(dist));

     q.push(s);//入列

     vis[s]=true;//记录为遍历过的点

     length=;

     node=s;

     while(!q.empty()){

         int u=q.front();

         q.pop();

         for(int i=head[u];i!=-;i=edge[i].next){//遍历每一条边

             int v=edge[i].to;

             if(!vis[v]&&dist[v]<dist[u]+edge[i].val){

                 vis[v]=true;

                 dist[v]=dist[u]+edge[i].val;//到v的最长路径

                 if(length<dist[v]){

                     length=dist[v];//不断更新最长路径

                     node=v;//更新节点

                 }

                 q.push(v);//重新入列，寻找下一个点

             }

         }

     }

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--){

         init();

         scanf("%d%d",&n,&m);

         for(int i=;i<n;i++){

             int u,v,val;

             scanf("%d%d",&u,&v);

             val=;//路径权值

             addedge(u,v,val);

             addedge(v,u,val);

         }

         bfs();//第一遍找到距离最远的端点

         bfs(node);//第二遍找最长距离

         int x=length+;//x为树的直径的节点个数

         while(m--){

             int k;

             scanf("%d",&k);

             if(k<=x) printf("%d\n",k-);//如果比树的直径短

             else{

                 int ans=length+(k-x)*;

                 printf("%d\n",ans);

             }

         }

     }

     return ;

 }

 /*

 1

 19 5

 1 2

 1 3

 2 4

 2 5

 3 6

 3 7

 4 8

 4 9

 8 12

 12 13

 9 14

 14 15

 15 16

 5 10

 5 11

 10 17

 17 18

 17 19

 7

 6

 10

 9

 11

 11

 12

 13

 15

 19

 */