tarjan离线：

参考博客：

https://www.dreamwings.cn/lca/4874.html

https://www.cnblogs.com/JVxie/p/4854719.html

复杂度：

$O(m+n)$，m是询问数，n是节点数。

伪代码：

Tarjan(u)   // merge和find为并查集合并函数和查找函数
{
    for each(u,v)       // 遍历u的所有子节点v
    {
        Tarjan(v);      // 继续往下遍历
        merge(u,v);     // 合并v到u这一集合
        标记 v 已被访问过;
    }
    for each(u,e)       // 遍历所有与u有查询关系的e
    {
        if (e 被访问过)
            u, e 的最近公共祖先为 find(e);
    }
}

模板：

int top,qtop;
int head[500010];
int qhead[500010];
int par[500010];
bool vis[500010];
struct edge
{
    int to;
    int next;
}eg[500010*2];
struct query
{
    int to;
    int id;
    int next;
}qu[500010*2];
int ans[500010];
void add(int a,int b)
{
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
void addq(int a,int b,int c)
{
    qu[qtop].to=b;
    qu[qtop].id=c;
    qu[qtop].next=qhead[a];
    qhead[a]=qtop++;
}
int Find(int x)
{
    if(par[x]==x)return x;
    return par[x]=Find(par[x]);
}
void tarjan(int id)
{
    vis[id]=true;
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int v=eg[i].to;
        if(!vis[v])
        {
            tarjan(v);
            par[v]=id;
        }
    }
    for(int i=qhead[id];i!=-1;i=qu[i].next)
    {
        int v=qu[i].to;
        if(vis[v])
            ans[qu[i].id]=Find(v);
    }
}
int main()
{
    int n,m,s,x,y;
    scanf("%d%d%d",&n,&m,&s);
    top=0;qtop=0;
    for(int i=1;i<=n;i++)
    {
        head[i]=-1;qhead[i]=-1;
        vis[i]=false;par[i]=i;
    }
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        addq(x,y,i);addq(y,x,i);
    }
    tarjan(s);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

倍增：

参考博客：

https://blog.csdn.net/qq_42790311/article/details/81486742

https://www.cnblogs.com/xqmmcqs/p/5954097.html

https://www.luogu.org/blog/34188/solution-p3379

复杂度：

$O(nlog_2n)$。

模板：

int top;
int head[500010];
int par[500010][25];//编号为i的结点的第2^j个祖先
int dep[500010];
int lg[500010];
struct edge
{
    int to;
    int next;
}eg[500010*2];
void add(int a,int b)
{
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
void dfs(int id,int fa,int depth)
{
    dep[id]=depth;
    par[id][0]=fa;
    //i的第2^j个祖先相当于i的第2^(j-1)个祖先的第2^(j-1)个祖先
    for(int i=1;(1<<i)<=dep[id];i++)
        par[id][i]=par[par[id][i-1]][i-1];
    for(int i=head[id];i!=-1;i=eg[i].next)
        if(eg[i].to!=fa)
            dfs(eg[i].to,id,depth+1);
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);//保证x的深度大于等于y
    while(dep[x]>dep[y])
        x=par[x][lg[dep[x]-dep[y]]-1];//让深的往上跳
    if(x==y)return x;
    //一起向上跳
    for(int i=lg[dep[x]]-1;i>=0;i--)
        if(par[x][i]!=par[y][i])
            x=par[x][i],y=par[y][i];
    return par[x][0];
}
int main()
{
    int n,m,r,x,y;
    scanf("%d%d%d",&n,&m,&r);
    lg[0]=0;
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);//预处理出log2(i)+1
    top=0;
    memset(head,-1,sizeof(head));
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(r,r,1);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}

树链剖分：

对于两个不在同一重链内的节点，让他们不断地跳，使得他们处于同一重链上。往上跳之后两点在同一条重链上，LCA就是两点中深度更小的那个。

int top;
int head[500010];
struct edge
{
    int to;
    int next;
}eg[1000010];
int par[500010];//该结点的父亲
int dep[500010];//该结点的深度
int tot[500010];//该结点子树的结点个数
int son[500010];//该结点的重儿子编号
int idx[500010];//该结点重新编号后的编号
int topp[500010];//该结点所在链的顶端结点
int cnt;
int ans;
void add(int a,int b)
{
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
int dfs1(int id,int fa,int depth)
{
    par[id]=fa;dep[id]=depth;
    tot[id]=1;
    int maxson=-1;
    son[id]=0;
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(temp==fa)continue;
        tot[id]+=dfs1(temp,id,depth+1);
        if(tot[temp]>maxson)
        {
            son[id]=temp;
            maxson=tot[temp];
        }
    }
    return tot[id];
}
void dfs2(int id,int topf)
{
    idx[id]=++cnt;
    topp[id]=topf;
    if(son[id]==0)return;     //子节点的son为0
    dfs2(son[id],topf);     //优先标记重儿子
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(idx[temp]==0)
            dfs2(temp,temp);     //每一条链以轻儿子为起点
    }
}
int lca(int x,int y)
{
    while(topp[x]!=topp[y])
    {
        if(dep[topp[x]]<dep[topp[y]])swap(x,y);     //谁的top低谁就往上走
        x=par[topp[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
int main()
{
    int n,m,r,x,y;
    scanf("%d%d%d",&n,&m,&r);
    for(int i=1;i<=n;i++)
    {
        head[i]=-1;
        idx[i]=0;
    }
    top=0;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs1(r,0,1);
    cnt=0;
    dfs2(r,r);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}