学步园

树的直径

题目已经说明是不会出现环了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int const MAXN = 100010;
typedef struct EDGE{
    int to;
    int w;
}Edge;
vector <Edge> edge[MAXN];
int vis[MAXN],dis[MAXN];
int n,m;
void Init(){
    for(int i = 0;i < MAXN;i++){
        edge[i].clear();
    }
}
void Add(int u,int v){
    Edge temp;
    temp.w = 1;
    temp.to = v;
    edge[u].push_back(temp);
    temp.to = u;
    edge[v].push_back(temp);
}
void Bfs(int start){
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    vis[start] = 1;
    dis[start] = 0;
    queue <int> q;
    while(!q.empty()){
        q.pop();
    }
    q.push(start);
    while(!q.empty()){
        int top = q.front();
        q.pop();
        for(int i = 0;i < edge[top].size();i++){
            int to = edge[top][i].to;
            if(!vis[to]){
                vis[to] = 1;
                dis[to] = dis[top] + edge[top][i].w;
                q.push(to);
            }
        }
    }
}
int Count(int start){
    int u = start,maxx = 0;
    Bfs(u);
    for(int i = 1;i <= n;i++){
        if(dis[i] > maxx){
            u = i;
            maxx = dis[i];
        }
    }
    Bfs(u);
    maxx = 0;
    for(int i = 1;i <= n;i++){
        if(dis[i] > maxx) maxx = dis[i];
    }
    return maxx;
}
int main(){
    int T,x;
    while(~scanf("%d",&T)){
        while(T--){
            Init();
            scanf("%d%d",&n,&m);
            for(int i = 0;i < n - 1;i++){
                int u,v;
                scanf("%d%d",&u,&v);
                Add(u,v);
                x = u;
            }
            int maxx;
            maxx = Count(x);
            while(m--){
                scanf("%d",&x);
                if(x - 1 <= maxx) printf("%d\n",x - 1);
                else printf("%d\n",2 * (x - maxx - 1) + maxx);
            }
        }
    }
    return 0;
}