【

题目】题意：N个城市形成一棵树，相邻城市之间的距离是1，问访问K个城市的最短路程是多少，共有M次询问(1 <= N, M <= 100000, 1 <= K <= N)。 【

思路】 访问K个城市的路线： 可以发现它由一条主线和若干支线构成，并且主线上的边只用访问一次，而支线上的边必须且只用访问两次。而题目给定的是一棵树，那么访问K的城市就必须且仅需要走K-1条边。总边数是固定的，我们只需要保证主线最长即可，所以就是

在树中找最长链。 【

找最长链】树形dp，dp[i]表示他的子树的最大深度。选一个树根开始访问，每次访问完根节点的子树都要找出子树中深度最深的两个，把他们加起来更新最长链长度。并且留下最深的深度+1当作根节点的深度。  

#include #include #include #include #include #include #define MID(x,y) ((x+y)/2)#define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int MAXN = 200005;struct node{    int u, v;    int next;}arc[MAXN];int en, head[MAXN];void init(){    en = 0;    mem(head, -1);}void insert(int u, int v){    arc[en].u = u;    arc[en].v = v;    arc[en].next = head[u];    head[u] = en ++;}int dp[MAXN];int maxlen;bool vis[MAXN];void dfs(int u){    vis[u] = 1;    int max1 = 0, max2 = 0;    int num = 0;    for (int i = head[u]; i != -1; i = arc[i].next){        int v = arc[i].v;        if (!vis[v]){            num ++;            dfs(v);            if (dp[v] > max1){                max2 = max1;                max1 = dp[v];            }            else{                if (dp[v] > max2){                    max2 = dp[v];                }            }        }    }    if (0 == num){        dp[u] = 0;    }    else{        if (num == 1)            maxlen = max(maxlen, max1+1);        else            maxlen = max(maxlen, max1+max2+2);        dp[u] = max1 + 1;    }    return ;}int main(){    //freopen("test.in", "r", stdin);    //freopen("test.out", "w", stdout);    int t;    scanf("%d", &t);    while(t --){        init();        int n, m;        scanf("%d %d", &n, &m);        for (int i = 0; i < n - 1; i ++){            int u, v;            scanf("%d %d", &u, &v);            insert(u, v);            insert(v, u);        }        mem(vis, 0);        mem(dp, 0);        maxlen = 0;        dfs(1);        for (int i = 0; i < m; i ++){            int tmp;            scanf("%d", &tmp);            if (tmp - 1 <= maxlen){                printf("%d\n", tmp - 1);            }            else{                printf("%d\n", maxlen + 2*(tmp-1-maxlen));            }        }    }    return 0;}