题目链接：https://www.nowcoder.com/acm/contest/15/C

题解：就是求虚树直径/2向上取整。


所谓虚树，其实就是把询问中需要用到的点建到另一棵树上，对于一些问题可以降低复杂度。比如我们询问一条链上的两个端点，直接做dfs的复杂度是O（N）的，但是对于虚树，这两个端点可以直接相连，它们之间的边记录了原本整条链上的信息，于是复杂度变成了O（1）。
那么怎么建虚树呢？除了用到给出的询问点，我们还会用到询问点之间的lca，但是求出所有点对之间的lca是O（N^2）级别的，较好的方式是，把询问点按dfs序排序，有三个点x、y、z,，他们按dfs序排序，lca（x，z）一定在lca（x，y）或者lca（y，z）中，以此类推，k个询问点只需要求k - 1个点对间的lca，然后，我们再次把所有点按dfs序排序、去重，准备工作完成后，就开始建树了，方法是，我们维护一个栈，如果栈为空，直接点入栈；否则，我们看栈顶元素是不是当前点的祖先，如果不是，那么弹出栈顶继续判断，否则就可以从栈顶元素向这个点连一条边再让当前点进栈了。具体判断栈顶元素是不是当前点的祖先的方式是dfs序，但光用一个数组（设为in数组）存储各节点的dfs序还不够，还要用另一个数组（设为out数组）存储各节点的子节点中最大的dfs序为多少，只有$in[u]<in[v]<=out[u]$，v才为u的子孙节点。第一个点就直接作为虚树的树根。然后两次DFS求直径。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5+5;
struct edge1{
    int v, next;
}E1[maxn*2];
struct edge2{
    int v, w, next;
}E2[maxn*2];
int head1[maxn], head2[maxn], edgecnt1, edgecnt2;
int n, dep[maxn], fa[maxn][20];
int dfsclk, in[maxn], out[maxn];
int t[maxn*4];//用来建立虚树
int pos, ans;//求树的直径,第一遍遍历到的最远叶子节点,树的直径
void init1(){
    memset(head1, -1, sizeof(head1));
    memset(head2, -1, sizeof(head2));
    edgecnt1 = dfsclk = edgecnt2 = 0;
}
void add1(int u, int v){
    E1[edgecnt1].v = v, E1[edgecnt1].next = head1[u], head1[u] = edgecnt1++;
}
void add2(int u, int v, int w){
    E2[edgecnt2].v = v, E2[edgecnt2].w = w, E2[edgecnt2].next = head2[u], head2[u] = edgecnt2++;
}
void dfs(int x, int pre){
    dfsclk++;
    in[x] = dfsclk;
    for(int i=head1[x]; ~i; i=E1[i].next){
        int v = E1[i].v;
        if(v == pre) continue;
        dep[v] = dep[x] + 1;
        fa[v][0] = x;
        dfs(v, x);
    }
    out[x] = dfsclk;
}
void init(){
    memset(dep, 0, sizeof(dep));
    memset(fa, 0, sizeof(fa));
    dfs(1, 0);
    int k = (int)floor(log(n)/log(2.0));
    for(int j=0; j+1<=k; j++){
        for(int i=1; i<=n; i++){
            if(fa[i][j]==0) fa[i][j+1]=0;
            else fa[i][j+1] = fa[fa[i][j]][j];
        }
    }
}
int getlca(int u, int v){
    int k = (int)floor(log(n)/log(2.0));
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=0; i<k; i++) if((dep[u]-dep[v])>>i&1) v=fa[v][i];
    if(u==v) return u;
    for(int i=k;i>=0;i--){
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}
bool cmp(int x, int y){
    return in[x]<in[y];
}
int build(int s){
    edgecnt2=0;
    sort(t, t+s, cmp);
    int curs = s;
    for(int i=1; i<curs; i++){
        t[s++] = getlca(t[i], t[i-1]);
    }
    sort(t, t+s, cmp);
    s = unique(t, t+s) - t;
    stack <int> st;
    st.push(t[0]);
    for(int i=1; i<s; i++){
        int u = t[i];
        while(!st.empty()&&!(in[st.top()]<in[u]&&out[st.top()]>=in[u])) st.pop();//条件说明st.top()必须为u的父亲节点（虚树而言），否则出栈
        int v = st.top();
        add2(u, v, dep[u]-dep[v]);
        add2(v, u, dep[u]-dep[v]);
        st.push(u);
    }
    return s;
}
//求虚树的直径
void dfs1(int x, int pre, int val){
    if(val>ans){
        ans = val;
        pos = x;
    }
    for(int i=head2[x];~i;i=E2[i].next){
        int v = E2[i].v;
        if(v == pre) continue;
        dfs1(v, x, val+E2[i].w);
    }
}
void dfs2(int x, int pre, int val){
    ans = max(ans, val);
    for(int i=head2[x];~i;i=E2[i].next){
        int v = E2[i].v;
        if(v == pre) continue;
        dfs2(v, x, val+E2[i].w);
    }
}
int main(){
    scanf("%d",&n);
    init1();
    for(int i=1; i<n; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add1(u, v);
        add1(v, u);
    }
    init();
    int q;
    scanf("%d", &q);
    while(q--){
        int s;
        scanf("%d", &s);
        for(int i=0; i<s; i++) scanf("%d", &t[i]);
        s = build(s);//建立虚树
        ans = 0;
        dfs1(t[0], 0, 0);
        ans = 0;
        dfs2(pos, 0, 0);
        printf("%d\n", (ans+1)/2);
        for(int i=0; i<s; i++) head2[t[i]]=-1;
    }
    return 0;
}