感受



思路



#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
const ll mod = 998244353;
struct edge{
    int v, nex;
}e[maxn << 1];
int fa[maxn][25];///fa[u][i] u向上跳2^i层所在的节点编号
int dep[maxn];
int head[maxn], cnt, n;
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    for(int i = 1; i <= n; i++){
        head[i] = -1;
    }
}
void dfs(int u, int f, int d){
    int v; dep[u] = d;
    fa[u][0] = f;
    for(int i = 1; i <= 20; i++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == f) continue;
        dfs(v, u, d + 1);
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int d = dep[u] - dep[v], i = 0; d; d >>= 1, i++){
        if(d & 1) u = fa[u][i];
    }
    /**u与v等深度*/
    if(u == v) return u;
    for(int i = 20; i >= 0; i--){
        if(fa[u][i] != fa[v][i]){
            u = fa[u][i]; v = fa[v][i];
        }
    }
    return fa[u][0];
}
int get(int x, int y){
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
int main(){
    scanf("%d", &n);
    init();
    int u, v;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    dfs(1, 0, 1);
    vector<int> vec;
    int q, num, x, ans; scanf("%d", &q);
    for(int i = 1; i <= q; i++){
        scanf("%d", &num);
        vec.clear(); x = 0; ans = 0;
        for(int j = 1; j <= num; j++){
            scanf("%d", &u);
            vec.push_back(u);
            if(dep[u] > dep[x]) x = u;
        }
        for(auto &itm : vec){
            ans = max(ans, get(itm, x));
        }
        printf("%d\n", (ans + 1) / 2);
    }
    return 0;
}