每日一题 7月8日 Alliances 点到树上点集的连通网的最短距离

题目链接：https://ac.nowcoder.com/acm/problem/13950
题目大意：
树上有k个帮派，每个帮派会占据一些城市。他们控制的点除了自己占领的点。还有再加上这些城市两两之间路径上的所有城市。

有时帮派之间会结盟，这样联盟的点集为这些帮派的点集的并集。他们控制的点除了自己占领的点。还有再加上这些城市两两之间路径上的所有城市。

现在有Q个询问。每次询问选择一个点作为首都。和一些帮派。我们只考虑这些被选择的帮派，并且他们结盟。首都离联盟控制的点最近距离为多少？

思路：我们先对所有的帮派求一个LCA。保存在LCA[i]。每次询问的帮派x1, x2, ...., xm。对LCA[x1], LCA[x2], ... , LCA[xm]求一个LCA。
1.如果首都root没有在LCA的子树里。那么最短距离为dis(root, LCA)。
2.如果在LCA的子树里面。
(1):如果root的子树有帮派原先占领的点。那么这个点到LCA一定经过root。距离为0。我们可以对每个帮派的点的dfs序排序二分。那么dfs序比in[root]大并且dfs最小的点最有可能是root的子树
(2):如果root的子孙没有被占领。那么可以把dfs序中他左边和右边离他最近的两个点拿出来和首都求LCA，这两个LCA里面一定有一个是离它最近的。（情况2其实可以合并在3里面处理）

#include <bits/stdc++.h>
using namespace std;

vector<int> G[500005];
int in[500005], out[500005], T=0;
struct LCA{
    int d[500005], fa[500005][22], lg[500005];
    void init(int n, int root){//预处理
        for(int i = 1; i <= n; ++i){
            lg[i] = lg[i-1] + (1 << lg[i-1] == i);
        }
        dfs(root, 0);
    }
    void dfs(int now, int father){
        in[now]=++T;
        fa[now][0]=father; d[now]=d[father]+1;
        for(int i=1; i<=lg[d[now]]; ++i){
            fa[now][i]=fa[fa[now][i-1]][i-1];
        }
        for(auto x: G[now]){
            if(x!=father){
                dfs(x, now);
            }
        }
        out[now]=T;
    }
    int lca(int x, int y){//LCA
        if(d[x]<d[y]) swap(x, y);
        while(d[x]>d[y]){
            x=fa[x][lg[d[x]-d[y]]-1];
        }
        if(x==y) return x;
        for(int k=lg[d[x]]-1; k>=0; --k){
            if(fa[x][k]!=fa[y][k]){
                x=fa[x][k], y=fa[y][k];
            }
        }
        return fa[x][0];
    }
    int dis(int x, int y){
        return d[x]+d[y]-2*d[lca(x, y)];
    }
}lca;

vector<int> b[500005], xw;
vector<pair<int, int> > dset[500005];//每个帮派的dfs序和点
int LCA[500005];

int slove(int root){
    int Lca=0;
    for(auto x: xw){
        if(Lca==0) Lca=LCA[x];
        else Lca=lca.lca(Lca, LCA[x]);
    }
    if(in[root]<in[Lca]||in[root]>out[Lca]){//在LCA的子树外
        return lca.dis(Lca, root);
    }
    int ans=1<<30;
    pair<int, int> pos1={0 , 0}, pos2={1<<30, 0};//在LCA的子树内
    for(auto x: xw){
        int pos=lower_bound(dset[x].begin(), dset[x].end(), make_pair(in[root], 0))-dset[x].begin();
        if(pos<=dset[x].size()-1){//求最大的小等于dfs[root]的点
            if(dset[x][pos].first<pos2.first){
                pos2=dset[x][pos];
            }
        }
        if(pos>0){//求最小的大等于dfs[root]的点
            pos--;
            if(dset[x][pos].first>pos1.first){
                pos1=dset[x][pos];
            }
        }
    }
    if(pos1.second){
        ans=min(ans, lca.dis(root, lca.lca(root, pos1.second)));
    }
    if(pos2.second){
        ans=min(ans, lca.dis(root, lca.lca(root, pos2.second)));
    }
    return ans;
}

int main(){
    int n, x, y, k; scanf("%d", &n);
    for(int i=1; i<n; i++){
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    lca.init(n+3, 1);
    scanf("%d", &k);
    for(int i=1; i<=k; i++){
        int m; scanf("%d", &m);
        while(m--){
            scanf("%d", &x);
            b[i].push_back(x);
        }
    }
    for(int i=1; i<=k; i++){
        int Lca=0;
        for(auto x: b[i]){
            dset[i].push_back({in[x], x});
            if(Lca==0) Lca=x;
            else Lca=lca.lca(Lca, x);
        }
        LCA[i]=Lca;
        sort(dset[i].begin(), dset[i].end());
    }
    int q; scanf("%d", &q);
    while(q--){
        int root, m;
        scanf("%d%d", &root, &m);
        xw.clear();
        for(int i=1; i<=m; i++){
            scanf("%d", &x);
            xw.push_back(x);//每次询问的帮派的集合
        }
        printf("%d\n", slove(root));
    }

    return 0;
}