前言:

这个每日一题对我来说稍微复杂了亿点点...

思路:

首先的题目的条件就是所有点的lca到所有点的路径都被标记了.我们要求点V到这些点集的一个最小距离.

假如这个点集的LCA和V的lca不是LCA的话,那么显然的一个结论距离就是V到lca的距离.

假如不是,那么V一定位于LCA的子树中.这是我们将树的dfs序求出,然后就简单了许多.距离就是要么是dfs序大于它的第一个点,要么就是小于它的第一个点.然后求个lca即可.

(看上去好像很简单...其实确实不难.)

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+50,M=20;
vector<int>g[N],q[N];
vector<int>x;
int f[N][M],dep[N],dfn[N],id,top[N];
void dfs(int u,int fa)
{
    dfn[u]=++id;dep[u]+=dep[fa]+1;
    f[u][0]=fa;for(int i=1;i<20;i++)    f[u][i]=f[f[u][i-1]][i-1];
    for(int v:g[u])
        if(v!=fa)    dfs(v,u);
}

int lca(int u,int v)
{
    if(dep[v]>dep[u])    swap(u,v);//假定u是dep大的.
    for(int i=19;i>=0;i--)
    {
        if(dep[f[u][i]]>=dep[v])    u=f[u][i];
    }if(u==v)    return v;
    for(int i=19;i>=0;i--)
    {
        if(f[u][i]!=f[v][i])    u=f[u][i],v=f[v][i];
    }return f[u][0];
}

int dis(int u,int v)    {return dep[u]+dep[v]-2*dep[lca(u,v)];}
bool cmp(int a,int b)    {return dfn[a]<dfn[b];}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }dfs(1,1);int t;scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        int u,v;scanf("%d",&u);
        for(int j=0;j<u;j++)
        {
            scanf("%d",&v);q[i].push_back(v);
            if(j==0)    top[i]=v;
            else        top[i]=lca(top[i],v);
        }sort(q[i].begin(),q[i].end(),cmp);
    }int Q;scanf("%d",&Q);
    while(Q--)
    {
        x.clear();int V,LCA;scanf("%d",&V);int u,v;scanf("%d",&u);
        for(int i=0;i<u;i++)
        {
            scanf("%d",&v);x.push_back(v);
            if(i==0)    LCA=top[v];
            else        LCA=lca(LCA,top[v]);
        }if(LCA!=lca(LCA,V))    printf("%d\n",dis(V,LCA));
        else
        {
            int ans=2e9;
            for(int e:x)
            {
                int sz=q[e].size();int pos=sz,r=sz-1,l=0;
                while(l<=r)
                {
                    int mid=(l+r)>>1;
                    if(dfn[q[e][mid]]>=dfn[V])    pos=mid,r=mid-1;
                    else                          l=mid+1;
                }
                if(pos!=0)    ans=min(ans,dis(V,lca(q[e][pos-1],V)));
                if(pos!=sz)   ans=min(ans,dis(V,lca(q[e][pos],V)));
            }printf("%d\n",ans);
        }
    }
    return 0;
}