LCA

向上标记法

时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)

如果两个结点不相同，就将较深的结点向上移动，直到移动到相同结点，那么该结点即为公共祖先结点。

代码

//预处理每个结点的深度，以及结点的父结点的编号
void dfs(int u, int father){
    depth[u]=depth[father]+1;
    fa[u]=father;

    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v!=father) dfs(v,u);
    }
}
//求u和v的公共祖先
int getlca(int u,int v){
    //只要u和v不同
    while(u!=v){
        //将深度大的结点向上移动
        if(depth[u]<depth[v]) v=fa[v];
        else u=fa[u];
    }
    return u;
}

倍增法

预处理 O ( n l o g n ) O(nlogn) O(nlogn)

• f a [ i ] [ j ] fa[i][j] fa[i][j] 表示从节点 i i i开始，向上走 2 j 2^j 2j步所走到节点的编号。若已经超出根节点, f a [ i ] [ k ] = 0 fa[i][k]=0 fa[i][k]=0。特别地, f a [ i ] [ 0 ] fa[i][0] fa[i][0]就是 i i i的根节点。

• d e p t h [ i ] depth[i] depth[i] 表示深度,根节点的深度为1,即 d e p t h [ r o o t ] = 1 depth[root]=1 depth[root]=1。

• 哨兵:如果从 i i i开始跳 2 j 2^j 2j步会跳过根节点,那么 f a [ i ] [ j ] = 0 fa[i][j]=0 fa[i][j]=0. d e p t h [ 0 ] = 0 depth[0]=0 depth[0]=0

• 递推关系： f a [ i ] [ k ] = f a [ f a [ i ] [ k − 1 ] ] [ k − 1 ] fa[i][k]=fa[fa[i][k-1]][k-1] fa[i][k]=fa[fa[i][k−1]][k−1]

询问 O ( l o g n ) O(logn) O(logn)

1. 先将两个点跳到同一层
2. 让两个点同时向上跳，直到他们最近公共祖先的下一层

代码

int ne[maxn],e[maxn],h[maxn],idx;
int fa[maxn][21],dep[maxn];
int root;
void bfs(){
    queue<int>q;
    q.push(root);
    dep[root]=1,dep[0]=0;
    // 哨兵depth[0] = 0: 如果从i开始跳2^j步会跳过根节点 
    // fa[fa[j][k-1]][k-1] = 0
    // 那么fa[i][j] = 0 dep[fa[i][j]] = dep[0] = 0
    while(q.size()){
        int t=q.front(); q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(dep[j]) continue;
            dep[j]=dep[t]+1;
            q.push(j);
            fa[j][0]=t;
            for(int k=1;k<=18;k++){ //注意边界
                fa[j][k]=fa[fa[j][k-1]][k-1];
            }
             /*
            举个例子理解超过根节点是怎么超过的
            因为我们没有对根节点fa[1][0]赋值,那么fa[1][0] = 0;
                 1
                / \
               2   3 
            fa[1][0] = 0;
            fa[2][0] = 1;
            fa[2][1] = fa[fa[2][0]][0] = fa[1][0] = 0;
            */
        }
    }
}

int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int k=18;k>=0;k--)
        if(dep[fa[x][k]]>=dep[y])
            x=fa[x][k];
    
    if(x==y) return x;
    for(int k=18;k>=0;k--){
        if(fa[x][k]!=fa[y][k]){
            x=fa[x][k];
            y=fa[y][k];
        }
    }

    return fa[x][0];
}

Tarjan

时间复杂度 O ( n + m ) O(n+m) O(n+m)，离线做法

思路

在深度优先遍历时，将节点分为三大类：

1. 正在搜索的分支
2. 已经遍历过,且回溯过
3. 还未搜索到的点

我们画一个图可以发现第一类点都像一颗颗果实挂在某个点上当我们枚举到一个点的时候另一个点是第1类点那么他们的最近公共祖先就是第1类点挂着的点

所以我们可以去搜索如果在搜索过程中标记点是第几类点回溯的时候枚举有关这个点的询问如果另一个点是第1类点我们就可以得到这组询问的最近公共祖先

如果另一个点不是第一类点就暂时不管因为我们这个点很快就会变成第1类点到时候再拿那个点来完成这组询问的计算，最后我们再把当前点并入父节点，然后当前点变成二类点，最后再统一输出一下就可以完成离线解最近公共祖先

代码

/*
在深度优先遍历时,将所有点分成三大类:
[0] 还未搜索到的点
[1] 正在搜索的分支
[2] 已经遍历过,且回溯过
*/
void tarjan(int u){
    st[u]=1;
    // u这条路上的根节点的左下的点用并查集合并到根节点
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(st[j]) continue;
        tarjan(j);
        p[j]=u; //从左下回溯后把左下的点合并到根节点
    }

    // 对于当前点u 搜索所有的询问，查看是否可以得出结果
    for(auto item:ask[u]){
        int y=item.first,id=item.second;
        if(st[y]==2){ //该点已被回溯，也就是经过了并查集的合并
            int anc=find(y);
            ans[id]=dis[u]+dis[y]-dis[anc]*2; //保持原本次序输出
        }
    }
    st[u]=2; //点u已经搜索完且要回溯了 就把st[u]标记为2 
}