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

书P375~380
以下规定：n为树的点数，m为询问次数
以下程序的模版题：http://acm.hdu.edu.cn/showproblem.php?pid=2586
例题：https://ac.nowcoder.com/acm/contest/1065/1009

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

②树上倍增法
设f[x,k]为x的第2^k辈祖先，则f[x,0]就是x的父节点
f[x,k]=f[f[x,k-1],k-1]
时间复杂度O((n+m) log n)

#include
using namespace std;
const int maxn=50000+1;
int f[maxn][20],d[maxn],dist[maxn];
int ver[2*maxn],Next[2*maxn],edge[2*maxn],head[maxn];
int T,n,m,tot,t;
queue q;
void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}
void bfs()
{
    q.push(1);
    d[1]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[i];
            if(d[y])
            {
                continue;
            }
            d[y]=d[x]+1;
            dist[y]=dist[x]+edge[i];
            f[y][0]=x;
            for(int j=1;j<=t;j++)
            {
                f[y][j]=f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}
int lca(int x,int y)
{
    if(d[x]>d[y])
    {
        swap(x,y);
    }
    for(int i=t;i>=0;i--)
    {
        if(d[f[y][i]]>=d[x])
        {
            y=f[y][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i=t;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        t=(int)(log(n)/log(2))+1;
        for(int i=1;i<=n;i++)
        {
            head[i]=d[i]=0;
        }
        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);
        }
        bfs();
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            cout<<dist[x]+dist[y]-2*dist[lca(x,y)]<<endl;
        }
    }
    return 0;
}

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

#include
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 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