求最近公共祖先的三种方法（LCA）

书P375~380
以下规定：n为树的点数，m为询问次数
http://acm.hdu.edu.cn/showproblem.php?pid=2586
luogu模版题：https://www.luogu.com.cn/problem/P3379

注意，多组数据一定要把所有变量清空！！！

①向上标记法
时间复杂度O(nm)

②树上倍增法

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,m,s;
int tot=0;
struct abc
{
    int t,nex;
};
int head[maxn];
abc e[maxn*2];
void add(int x,int y)
{
    tot++;
    e[tot].t=y;
    e[tot].nex=head[x];
    head[x]=tot;
    return ;
}
int fa[maxn][20],lg[maxn],depth[maxn];
void init()
{
    for(int i=1;i<=n-1;i++)
    {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    return ;
}
void dfs(int x,int fath)
{
    fa[x][0]=fath,depth[x]=depth[fath]+1;
    for(int i=1;i<=lg[depth[x]]-1;i++)
    {
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int i=head[x];i!=0;i=e[i].nex)
    {
        if(e[i].t!=fath)
        {
            dfs(e[i].t,x);
        }
    }
    return ;
}
int LCA(int x,int y)
{
    if(depth[x]<depth[y])    swap(x,y);
    while(depth[x]>depth[y])
    {
        x=fa[x][lg[depth[x]-depth[y]]-1];
    }
    if(x==y)    return x;
    for(int i=lg[depth[x]]-1;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    init();
    dfs(s,0);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}

③Tarjan算法
时间复杂度O(n+m)

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+1;
int ver[2*maxn],Next[2*maxn],edge[2*maxn],head[2*maxn];
int fa[maxn],d[maxn],v[maxn],lca[maxn],ans[maxn];
vector<int> query[maxn],query_id[maxn];
int T,n,m,tot,t;
void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}
void add_query(int x,int y,int id)
{
    query[x].push_back(y),query_id[x].push_back(id);
    query[y].push_back(x),query_id[y].push_back(id);
}
int get(int x)
{
    if(x==fa[x])
    {
        return x;
    }
    return fa[x]=get(fa[x]);
}
void tarjan(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(v[y])
        {
            continue;
        }
        d[y]=d[x]+edge[i];
        tarjan(y);
        fa[y]=x;
    }
    for(int i=0;i<query[x].size();i++)
    {
        int y=query[x][i],id=query_id[x][i];
        if(v[y]==2)
        {
            int lca=get(y);
            ans[id]=min(ans[id],d[x]+d[y]-2*d[lca]);
        }
    }
    v[x]=2;
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            head[i]=0;fa[i]=i;v[i]=0;
            query[i].clear();query_id[i].clear();
        }
        tot=0;
        for(int i=1;i<=n-1;i++)
        {
            int x,y,z;
            cin>>x>>y>>z;
            add(x,y,z);
            add(y,x,z);
        }
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            if(x==y)
            {
                ans[i]=0;
            }
            else
            {
                add_query(x,y,i);
                ans[i]=1<<30;
            }
        }
        tarjan(1);
        for(int i=1;i<=m;i++)
        {
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

参考文章：https://blog.csdn.net/qq_45432665/article/details/106038095