在线倍增算法

在线倍增算法

讲解可以看这个文章:最近公共祖先（lca）,下面是我的模板:

const int N=500000+7;
int n,m,s;
int tot;
int first[N],d[N],p[N][21];
struct edge
{
    int v,next;
} e[2*N];
void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=first[u];
    first[u]=tot++;
}
void dfs(int u,int fa)
{
    d[u]=d[fa]+1;
    p[u][0]=fa;
    for(int i=1; (1<<i)<=d[u]; i++)
        p[u][i]=p[p[u][i-1]][i-1];
    for(int i=first[u]; ~i; i=e[i].next)
    {
        int v=e[i].v;
        if(v!=fa)
            dfs(v,u);
    }
}
int lca(int a,int b)
{
    if(d[a]>d[b]) swap(a,b);//保证a在b点的上方
    for(int i=20; i>=0; i--)
        if(d[a]<=d[b]-(1<<i))
            b=p[b][i];  //把b移到和a同一个深度
    if(a==b) return a;
    for(int i=20; i>=0; i--)
    {
        if(p[a][i]==p[b][i])
            continue;
        else
            a=p[a][i],b=p[b][i];//一起向上跳跃
    }
    return p[a][0];
}
void init()
{
    tot=0;
    mem(first,-1);
    mem(d,0);
    mem(p,0);
}
int main()
{
    init();
    int a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&a,&b);
        add_edge(a,b);
        add_edge(b,a);
    }
    dfs(s,0);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    return 0;
}