附：

LCA问题简述

自己是自己的祖先

向上标记法

一般不用

• 从x向上走到根节点， 并标记路径上经过的点
• 从y向上走到根节点， 当遇到第一个被标记的点就找到了LCA(x, y)

倍增法

倍增的意思就是们不用每次向上爬一个，而是向上爬2^n个

具体分析看：

步骤： 每次向上爬2^n

• [1] 先将两个点跳到同一层
• [2] 让两个点同时往上跳，一直跳到它们的最近公共祖先的下一层。

数据定义：

• fa[i][j]表示从i开始，向上走2^j步所能走到的结点。0 <= j <= logn
• dep[i]表示深度
• • 哨兵：如果从i开始跳2^j步会跳过根结点，那么fa[i][j] = 0。dep[0] = 0

预处理：

1. 结点深度：
   深度的更新就是他爸爸的深度+1
2. 结点\(2^i\)级的祖先
   由于\(2^{(j-1)} +2^{(j-1)}=2^j\)
   所以：
   i的\(2^{(j-1)}\)级祖先的\(2^{(j-1)}\)级祖先 就是i的2^j级祖先。
   故：
   fa[i][j]=fa[fa[i][j-1]][j-1]

复杂度：

• 预处理 O(nlogn)
• 查询 O(logn)

讲解代码

模板题洛谷p3379

#include 
#include 
#include  
#include 
#include 
#include 
using namespace std;
const int maxn=500005;
vector  e[maxn];
int n,m,s,dep[maxn],fa[maxn][21];
int read() //快读 
{ 
    int ans=0,flag=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            flag=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    } 
    return ans*flag; 
} 
void dfs(int x,int father) //x为当前节点，father为他的爸爸
{
    dep[x]=dep[father]+1; //x的深度是他父亲的深度+1
    fa[x][0]=father; //2^0是1，x向上一个的祖先就是他爸爸
    for(int i=1;(1<=0;i--) //(int)(log(n)/log(2))就是n以内最大的2的次方，从最大的开始倍增
    {
        if(fa[u][i]!=fa[v][i]) //如果他们的爸爸不相同，即没有找到LCA
        {
            u=fa[u][i]; 
            v=fa[v][i]; //一起倍增
        }
    }
    return fa[u][0]; //返回他们的爸爸，即是LCA   
}
int main()
{
    n=read();
    m=read();
    s=read();
    for(int i=1;i<=n-1;i++)
    {
        int x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x); //vector存图 
    }
    dfs(s,0); //预处理 
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        int ans=lca(x,y);
        printf("%d\n",ans); 
    }
    return 0; 
}

模板代码

模板题洛谷p3379

#include 
#include 
#include  
#include 
#include 
#include 
using namespace std;
const int maxn=500005;
vector  g[maxn];
int n,m,s,dep[maxn],fa[maxn][21];

void dfs(int x,int f){
    dep[x]=dep[f]+1;
    fa[x][0]=f;
    for(int i=1;(1<dep[u]) swap(v,u);
    int temp=dep[u]-dep[v];
    for(int i=0;(1<=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i],v=fa[v][i];
        }
    }
    return fa[u][0];
}

int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n-1;i++)
    {
       int x,y;cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(s,0);
    
    for(int i=0;i>x>>y;
        int ans=lca(x,y);
        printf("%d\n",ans); 
    }
    return 0; 
}

Tarjan——离线求LCA O(n+m)

在深度优先遍历时，将所有点分成三大类：

• [1] 已经遍历过，且回溯过的点
• [2] 正在搜索的分支
• [3] 还未搜索到的点

模板代码