LCA算法详解

使用链式前向星。

DFS函数处理某个点第$2^i$的父亲关系。

lca函数中不要忘了拉平(将a,b点拉至同一深度)最后用倍增算法找父亲。

$\log_{2}{} $的预处理直接使用 $log2()$ 函数即可。

链式前向星的道路数组要开$2$倍。

#include<bits/stdc++.h>
using namespace std;
int N,M,S;
struct edge{
    int t,nx;
} r[500002&lt;&lt;1];
int rf[500002],rcnt;
void add(int a,int b){//链式前向星
    rcnt++;
    r[rcnt].t=b;
    r[rcnt].nx=rf[a];
    rf[a]=rcnt;
    return;
}
int lg[500002],depth[500002],fa[500002][22];
void dfs(int now,int fat){//找2^i次方的fa  now现在所在的节点 fat该节点的fa
    fa[now][0]=fat;
    depth[now]=depth[fat]+1;
    for(int i=1;i&lt;=lg[depth[now]];i++){
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    int cnt=rf[now];
    while(cnt&gt;0){
        if(r[cnt].t!=fat) dfs(r[cnt].t,now);
        cnt=r[cnt].nx;
    }
    return;
}
int lca(int a,int b){
    if(depth[a]&lt;depth[b]){
        swap(a,b);
    }
    while(depth[a]&gt;depth[b]){
        a=fa[a][lg[depth[a]-depth[b]]];
    }
    if(a==b){
        return a;
    }
    for(int i=lg[depth[a]];i&gt;=0;i--){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
int main(){
    // freopen(&quot;1in&quot;,&quot;r&quot;,stdin);
    // freopen(&quot;1out&quot;,&quot;w&quot;,stdout);
    cin&gt;&gt;N&gt;&gt;M&gt;&gt;S;
    for(int i=1;i&lt;N;i++){
        int x,y;
        cin&gt;&gt;x&gt;&gt;y;
        add(x,y);
        add(y,x);
    }

    for(int i=1;i&lt;=N;i++){
        lg[i]=log2(i);
    }

    dfs(S,0);

    for(int i=1;i&lt;=M;i++){
        int x,y;
        cin&gt;&gt;x&gt;&gt;y;
        cout&lt;&lt;lca(x,y)&lt;&lt;endl;
    }
    return 0;
}