URAL/1329

来自"NOCOW"

又是lca

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxn=40010,maxm=(maxn<<1);
int n,l,res,ace,dep=0,tot=0,stk[maxn],f[maxm<<2]={0};
int *d,*p,pos[maxm]={0},t[maxm],dist[maxn]={0};
int *h,head[maxn]={0},node[maxm],next[maxm];
bool *v,visit[maxn]={false};
void addedge(int a,int b)
{
    node[++tot]=b;
    next[tot]=h[a];
    h[a]=tot;
}
void dfs()
{
    int a,b,top=0;
    v[stk[++top]=-1]=true;
    d[-1]=0;
    while (top)
    {
        t[++tot]=a=stk[top];
        if (!p[a])  p[a]=tot;
        while (h[a] && v[node[h[a]]])  h[a]=next[h[a]];
        if (h[a])
        {
            b=node[h[a]];
            stk[++top]=b;
            v[b]=true;
            d[b]=d[a]+1;
        }
        else  --top;
    }
}
void swap(int& a,int& b)
{
    a^=b;
    b^=a;
    a^=b;
}
int lca(int a,int b)
{
    if (a > b)  swap(a,b);
    int l=a+res-1,r=b+res-1,ans;
    if (d[f[l]] < d[f[r]])  ans=f[l];
    else  ans=f[r];
    for (;l^r^1;l>>=1,r>>=1)
    {
        if (l&1^1)  if (d[f[l^1]] < d[ans])  ans=f[l^1];
        if (r&1)  if (d[f[r^1]] < d[ans])  ans=f[r^1];
    }
    return ans;
}
int main()
{
    int a,b;
    v=visit+1,h=head+1,d=dist+1,p=pos+1;
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    tot=0;
    for (int i=-1;i<maxn-1;++i)  d[i]=maxn;
    dfs();
    while ((1<<dep) < (tot<<1))  ++dep;
    res=(1<<dep-1);
    for (int i=1;i<=tot;++i)  f[i+res-1]=t[i];
    while (--dep)
        for (int i=(1<<dep-1);i<(1<<dep);++i)
            if (d[f[i<<1]] < d[f[(i<<1)+1]])  f[i]=f[i<<1];
            else  f[i]=f[(i<<1)+1];
    scanf("%d",&l);
    for (int i=1;i<=l;++i)
    {
        scanf("%d%d",&a,&b);
        ace=lca(p[a],p[b]);
        if (ace == a)  printf("1\n");
        else if (ace == b)  printf("2\n");
        else  printf("0\n");
    }
    return 0;
}
//by zzy