Alliances

题目：
有n个城市，有(n-1)条道路，每条路连接两个城市，城市和道路构成了一棵n个节点的树。
有k个帮派，每个帮派占领ci个城市。
帮派集合称为联盟，他们控制的城市为他们占领的城市和所占领的城市二二之间的城市。
有q个询问，每个询问给出一个首都和一个联盟，求首都距离联盟所控制的城市最近的距离？

思路：
在树中求最短路时使用Lca,先求出每一个帮派所控制的深度最小的节点（既该帮派所占领的节点的最近公共祖先），然后在每一个询问中求出该联盟所控制的深度最小的节点。
①：该节点为首都节点的祖宗节点：
对联盟中的每一个帮派中所占领的节点中找在中序遍历在首都节点最近的左右二个节点（因为最近的点与首都节点的最近公共祖先是与首都节点最近的），并求出节点与首都节点的深度最大的祖宗节点（最近公共祖先），最后求祖宗节点与首都节点的距离并对结果进行更新。
②：该节点不为首都节点的祖宗节点：
直接求该节点与首都节点的距离。

代码：

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

typedef long long ll;

inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        {
            f=-f;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return f*x;
}

vector<int> g[500005], b[500005];
int dep[1000005], vs[1000005], id[500005], ji=0, st[20][1000005], la[500005], vi[500005];
void dfs(int v,int f,int d)
{
    vs[ji]=v;
    dep[ji]=d;
    id[v]=ji;
    ji++;
    for(int i=0; i<g[v].size(); i++)
    {
        if(f!=g[v][i])
        {
            dfs(g[v][i],v,d+1);
            dep[ji]=d;
            vs[ji++]=v;
        }
    }
}

int lca(int u,int v)
{
    int x=id[u], y=id[v];
    if(x>y)
    {
        swap(x,y);
    }
    if(x==y)
    {
        return vs[x];
    }
    int l=(int)log2(y-x), p;
    if(dep[st[l][x]]<dep[st[l][y-(1<<l)+1]])
    {
        p=st[l][x];
    }
    else
    {
        p=st[l][y-(1<<l)+1];
    }
    return vs[p];
}

int dis(int x,int y)
{
    return dep[id[x]]+dep[id[y]]-2*dep[id[lca(x,y)]];
}

int main()
{
    memset(la,-1,sizeof(la));
    int n;
    n=read();
    for(int i=0; i<n-1; i++)
    {
        int u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,-1,0);
    for(int i=0; i<ji; i++)
    {
        st[0][i]=i;
    }
    for(int k=1; (1<<k)<=ji; k++)
    {
        for(int i=0; i+(1<<k)-1<ji; i++)
        {
            if(dep[st[k-1][i]]>dep[st[k-1][i+(1<<(k-1))]])
            {
                st[k][i]=st[k-1][i+(1<<(k-1))];
            }
            else
            {
                st[k][i]=st[k-1][i];
            }
        }
    }
    int k=read();
    for(int i=1; i<=k; i++)
    {
        int c=read();
        while(c--)
        {
            int v=read();
            if(la[i]==-1)
            {
                la[i]=v;
            }
            else
            {
                la[i]=lca(la[i],v);
            }
            b[i].push_back(id[v]);
        }
        sort(b[i].begin(),b[i].end());
    }
    int q=read();
    while(q--)
    {
        int x=read(), t=read(), d=inf, p=-1;
        for(int i=0; i<t; i++)
        {
            vi[i]=read();
            if(p==-1)
            {
                p=la[vi[i]];
            }
            else
            {
                p=lca(p,la[vi[i]]);
            }
        }
        if(p==lca(x,p))
        {
            int l, r;
            for(int i=0; i<t; i++)
            {
                r=lower_bound(b[vi[i]].begin(),b[vi[i]].end(),id[x])-b[vi[i]].begin();
                l=r-1;
                if(r<b[vi[i]].size())
                    d=min(dis(lca(vs[b[vi[i]][r]],x),x),d);
                if(l>=0)
                    d=min(dis(lca(vs[b[vi[i]][l]],x),x),d);
            }
            printf("%d\n",d);
        }
        else
        {
            printf("%d\n",dis(p,x));
        }
    }
    return 0;
}