LCA board

LCA The board

Variable ：

$int$$fa[N][25](The\; second\; dimension\; depends\; onNsize\; ,\; Jump\; watch)$
$int$$dep[N](Point\; depth)$
$int$$h[N],e[M],ne[M],idx(Adjacency\; list)$

$seek$$dfs$$Ordinal\; variable\; ：$

$int$$timestamp$
$int$$dfn[N]$

The key function ：

void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void bfs(int root){
    memset(dep,0x3f,sizeof dep);
    dep[root]=1;
    dep[0]=0;// sentry 
    queue<int>q;
    q.push(root);
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dep[j]>dep[t]+1){
                dep[j]=dep[t]+1;
                q.push(j);
                // Pre processing skip table 
                fa[j][0]=t;
                for(int k=1;k<=25;k++){
                    fa[j][k]=fa[fa[j][k-1]][k-1];// Multiply 
                }
            }
        }
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    // Let's go high first dep Jump to and low dep Same floor 
    for(int k=25;k>=0;k--){
        if(dep[fa[a][k]]>=dep[b])a=fa[a][k];// Sentinels work here 
    }
    if(a==b)return a;// You can return to any one at this time a and b It means the same number 
    // If the two numbers are not equal , Find the nearest public ancestor 
    for(int k=25;k>=0;k--){
        if(fa[a][k]!=fa[b][k]){
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}

$dfsOrder\; function:$

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;dfn[u]=++timestamp;
    for(int k=1;k<=20;k++)f[u][k]=f[f[u][k-1]][k-1];
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs(j,u);
    }
}