LCA 倍增模闆

感謝大佬模闆，想要看更加精彩的講解搓這裡

構造通路數組:

void make_bin()
{
    bin[]=;
    for(int i=;i<=;i++)
        bin[i]=bin[i-]<<;
}
           

構造鄰接表：

void Link()
{
    for(int i=;i<=n-;i++){//n- edges;or you can define a m pointing to the number of edges;
        scanf("%d%d",&u[i],&v[i]);
        //u[i+n-]=v[i];v[i+n-]=u[i];//雙向; 
        next[i]=first[u[i]];
        //next[i+n-]=first[v[i]];//雙向;
        first[u[i]]=i;
        //first[v[i]]=i+n-;//雙向;
        isroot[v[i]]=true;
    }
}
           

寬搜：

void bfs()
{
    int head=,tail=;
    q[0]=root,vis[root]=true;
    while(head^tail){
        int now=q[head];head++;
        for(int i=;i<=;i++){
            if(bin[i]<=deep[now])
                fa[now][i]=fa[fa[now][i-]][i-];
            else break;
        }
        for(int i=first[now];i;i=next[i])
            if(!vis[v[i]]){
                vis[v[i]]=true;
                fa[v[i]][]=now;
                deep[v[i]]=deep[now]+;
                q[tail++]=v[i];
            }
    }
}
           

求lca:

int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    for(int i=;i<=;i++)
        if(t&bin[i])x=fa[x][i];
    for(int i=;i>=;i--)
        if(fa[x][i]^fa[y][i])
            x=fa[x][i],y=fa[y][i];
    if(!(x^y))return y;
    return fa[x][];
}
           

入門題:POJ1330

複雜度為 nlogn

題目代碼:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define mst(x,y) memset(x,y,sizeof(x));
using namespace std;
const int maxn = e4+;
int father[maxn][];
int u[maxn],v[maxn];
int first[maxn],next[maxn],depth[maxn],q[maxn];
bool isroot[maxn];
int bin[];
int n;
int root;
bool vis[maxn];
void make_bin(){
    bin[] = ;
    for(int i=;i<=;i++){
        bin[i] = bin[i-]<<;
    }
}
void link(){
    for(int i=;i<n;i++){
        scanf("%d %d",&u[i],&v[i]);
        next[i] = first[u[i]];
        first[u[i]] = i;
        isroot[v[i]] = true;
    }
    for(int i=;i<=n;i++){
        if(!isroot[i]){
            root = i;
            break;
        }
    }
}
void bfs(){
    int head = ,tail = ;
    q[0] = root;vis[root] = true;
    while(head^tail){
        int now = q[head];head++;
        for(int i=;i<=;i++){
            if(bin[i] < depth[now]){
                father[now][i] = father[father[now][i-]][i-];
            }else{
                break;
            }
        }
        for(int i=first[now];i;i=next[i]){
            if(!vis[v[i]]){
                vis[v[i]] = true;
                father[v[i]][] = now;
                depth[v[i]] = depth[now]+;
                q[tail++] = v[i];
            }
        }
    }
}
int lca(int x,int y){
    if(depth[x] < depth[y]){
        swap(x,y);
    }
    int t = depth[x]  - depth[y];
    for(int i=;i<=;i++){
        if(t&bin[i]) x = father[x][i];
    }
    for(int i=;i>=;i--){
        if(father[x][i]^father[y][i]){
            x=father[x][i];y=father[y][i];
        }
    }
    if(!(x^y)) return y;
    return father[x][];
}
void init(){
    mst(vis,false);
    mst(isroot,false);
    mst(u,);
    mst(v,);
    mst(first,);
    mst(next,);
    mst(father,);
    mst(depth,);
    mst(q,);
}
int main(){
    int t;
    make_bin();
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d",&n);
        link();
        bfs();
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return ;
}