题意：N个城市形成一棵树，相邻城市之间的距离是1，问游K个城市的最短路程是多少，共有M次询问(1 <= N, M <= 100000, 1 <= K <= N)。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4607
——>>把这棵树拉直，得最长路（直径）共有maxd个城市，如果K <= maxd，只要一直向前走，路程为K - 1；如果K > maxd，贪心策略为最长路一定要从头走到尾，中间补上缺少的城市，每补一个，距离+2，结果是maxd - 1 + (K - maxd) * 2。
对于最长路（直径），可用无根树转有根树，第一次任选一点作根转一次，然后找出最深的叶子，第二次以这个最深的叶子为根转一次，树的层数就是最长路的长度。
#include <cstdio>
#include <vector>using namespace std;const int maxn = 100000 + 10;
vector<int> G[maxn];
int d[maxn];void dfs(int u, int fa, int cur) //现在的点为u，其父结点为fa，从根到u的经过cur个点
{d[u] = cur;int cnt = G[u].size();for(int i = 0; i < cnt; i++){int v = G[u][i];if(v != fa) dfs(v, u, cur+1);}
}int main()
{int T, N, M, u, v, i, j, K;scanf("%d", &T);while(T--){scanf("%d%d", &N, &M);for(i = 1; i <= N; i++) G[i].clear();for(i = 0; i < N-1; i++){scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}dfs(1, 0, 1); //第一次转有根树，找一个最长路的一端j = 1;for(i = 2; i <= N; i++) if(d[i] > d[j]) j = i;dfs(j, 0, 1); //第二次转有根树，找最长路j = 1;for(i = 2; i <= N; i++) if(d[i] > d[j]) j = i;int maxd = d[j], ret;for(i = 0; i < M; i++){scanf("%d", &K);if(K <= maxd) ret = K - 1;else ret = maxd - 1 + (K - maxd) * 2;printf("%d\n", ret);}}return 0;
}