题意：有n个景点，n-1条边，相连点间的距离为1，问遍历k个点，求最小的步行距离。
思路：
1.求出这棵树的最长直径，如果k小于最长直径len ，则最小距离为k-1，否则为（k-1en)*2+len-1；
2.如何求一棵树的最长直径。从任一个点BFS，最后进队列的点必为直径两个端点中的一个。再以该点为起点DFS求出树的直径。
//406MS 2988K
#include
#include
#include
using namespace std;
const int M = 100005;
int deg[M];
struct Edge
{
int to,nxt;
} edge[M<<1];
int head[M],ep,maxn,vis[M],src,n;
int max (int a,int b)
{
return a > b ? a : b;
}
void addedge (int cu,int cv)
{
edge[ep].to = cv;
edge[ep].nxt = head[cu];
head[cu] = ep ++;
}
void DFS (int u,int dep)
{
maxn = max (maxn,dep);
vis[u] = 1;
for (int i = head[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].to;
if (!vis[v])
DFS (v,dep+1);
}
}
void BFS(int u)
{
int que[M+100];
int front ,rear,i,v;
front = rear = 0;
que[rear++] = u;
vis[u] = 1;
while (front != rear)
{
u = que[front ++];
front = front % (n+1);
for (i = head[u];i != -1;i = edge[i].nxt)
{
v = edge[i].to;
if (vis[v]) continue;
vis[v] = 1;
que[rear++] = v;
rear = rear%(n+1);
}
}
src = que[--rear];//求出其中一个端点
}
int main ()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
int T,m,i;
int u,v,k;
scanf ("%d",&T);
while (T --)
{
scanf ("%d%d",&n,&m);
memset (head,-1,sizeof(head));
ep = 0;
for (i = 0; i < n-1; i ++)
{
scanf ("%d%d",&u,&v);
addedge (u,v);
addedge (v,u);
}
memset (vis,0,sizeof(vis));
BFS(1);
// printf ("src:%d\n",src);
memset (vis,0,sizeof(vis));
maxn = 0;
DFS (src,1);
// printf ("maxn:%d\n",maxn);
while (m --)
{
scanf ("%d",&k);
if (k <= maxn)
printf ("%d\n",k-1);
else
printf ("%d\n",(k - maxn)*2+maxn-1);
}
}
}