题目大意：给定一棵树，让求出依次访问k个点的最小花费，每条边的权值都为1.
思路：如果能一直往下走不回来，那么这个路径肯定是最小的，这就取决于给定的k，但是怎么确定这个能一直走的长度呢，其实这个就是树的直径，也叫作最长简单路径。找出来这个直径之后，只需和k比较一下就能确定走多少步。设直径为maxx， 如果maxx + 1== k的话，说明刚好不用回来走完最长的这个路，所以当k小于等于maxx + 1的时候就是k-1，当k大于maxx + 1的时候，除了要走完不用回来的路，肯定还要走那些用回来的，剩下的要回来的个数是k-maxx-1,这些都走两遍，所以乘以二就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int maxn = ;
int tot, head[maxn];
struct Edge {
int to, next;
}edge[maxn];
bool vis[maxn];
void init()
{
tot = ;
memset(head, -, sizeof(head));
}
void addedge(int u, int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
int maxx, pos;
void bfs(int p)//广搜找出离p最远的那个点
{
maxx = ;
memset(vis, false, sizeof(vis));
queue<pii> Q;
pii cur, nex;
cur.first = p; cur.second = ;
vis[p] = true;
Q.push(cur);
while (!Q.empty())
{
cur = Q.front();
Q.pop();
for (int i = head[cur.first]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if (vis[v]) continue;
vis[v] = true;
nex.first = v; nex.second = cur.second + ;
if (maxx < nex.second)
{
maxx = nex.second;//最远的距离保存在maxx中
pos = v;//最远的那个点保存在pos中
}
Q.push(nex);
}
}
}
int main()
{
int T, n, m;
scanf("%d", &T);
while (T--)
{
init();
int u, v;
scanf("%d %d", &n, &m);
for (int i = ; i < n; i++)
{
scanf("%d %d", &u, &v);
addedge(u, v);
addedge(v, u);
}
bfs();
bfs(pos);
int k;
for (int i = ; i < m; i++)
{
scanf("%d", &k);
if (k - <= maxx)
printf("%d\n", k - );
else
printf("%d\n", maxx + (k - maxx - ) * );
}
} return ;
}