两边bfs求解。
第一遍bfs求出直径的某一个顶点。
第二次bfs求出直径的另一个顶点。
第一遍bfs求出直径的某一个顶点。
第二次bfs求出直径的另一个顶点。
然后直径的长度出来了。直接求解就可以了。
#include<string.h>
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<queue>
using namespace std;
#define maxn 200005
struct list
{int next;int v;
}node[maxn];
int head[maxn];
int num;
int len,ns;
int n,m;
void add(int l,int r)
{node[num].v=r;node[num].next=head[l];head[l]=num++;
}
void bfs(int p)
{int dist[maxn];for(int i=1;i<=n;i++)dist[i]=9999999;queue<int>q;q.push(p);dist[p]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=head[x];i!=-1;i=node[i].next){int e=node[i].v;if(dist[e]>dist[x]+1){dist[e]=dist[x]+1;q.push(e);}}}len=0;for(int i=1;i<=n;i++){if(len<dist[i]&&dist[i]!=9999999){len=dist[i];ns=i;}}
}
int main()
{int T,i,a,b,k;scanf("%d",&T);while(T--){num=0;memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(i=0;i<n-1;i++){scanf("%d%d",&a,&b);add(a,b);add(b,a);}bfs(1);bfs(ns);while(m--){scanf("%d",&k);if(k<=len+1)printf("%d\n",k-1);else printf("%d\n",len+(k-len-1)*2);}}return 0;
}