lca 模板

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=500000+5;
const int M=2*500000+5;
struct Edge
{
    int nex,v,to;
}edge[M];
int lg[N],head[M],pos;
void init(int n)//常数优化
{
    pos=0;
    CLR(head,0);
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}
void add(int a,int b)
{
    edge[++pos].nex=head[a];
    head[a]=pos;
    edge[pos].to=b;
}

int fa[N][100];
int deth[N];
void dfs(int cur,int fath)
{
    deth[cur]=deth[fath]+1;
    fa[cur][0]=fath;
    for(int i=1;(1<<i)<=deth[cur];i++)
    fa[cur][i]=fa[ fa[cur][i-1] ][i-1];

    for(int i=head[cur];i;i=edge[i].nex)
    if(edge[i].to!=fath)
        dfs(edge[i].to,cur);
}
int lca(int x,int y)
{
    if(deth[x]<deth[y])
        swap(x,y);
    while(deth[x]>deth[y])
        x=fa[x][ lg[ deth[x]-deth[y] ]-1];

    if(x==y)return x;
    for(int k=lg[deth[x]]-1;k>=0;k--)
        if(fa[x][k]!=fa[y][k])
        x=fa[x][k],y=fa[y][k];

    return fa[x][0];
}
int main()
{
    int n,m,root;
    RIII(n,m,root);
    init(n);
    rep(i,1,n-1)
    {
        int a,b;RII(a,b);
        add(a,b);add(b,a);
    }

    dfs(root,0);
    while(m--)
    {
        int a,b;RII(a,b);
        printf("%d
",lca(a,b));
    }
    return 0;
}

View Code

想要实现这个算法，首先我们要记录各个点的深度和他们 $2^i2i级的的祖先，用数组 m{depth}depth表示每个节点的深度，fa[i][j]fa[i][j]表示节点ii的2^j2j级祖先。代码如下：$

void dfs(int f,int fath) //f表示当前节点，fath表示它的父亲节点
{
depth[f]=depth[fath]+1;
fa[f][0]=fath;
for(int i=1;(1<<i)<=depth[f];i++)
  fa[f][i]=fa[fa[f][i-1]][i-1]; //这个转移可以说是算法的核心之一
                                //意思是f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
                                //2^i=2^(i-1)+2^(i-1)
for(int i=head[f];i;i=e[i].nex)
  if(e[i].t!=fath)
    dfs(e[i].t,f);
}

预处理完毕后，我们就可以去找它的LCA了，为了让它跑得快一些，我们可以加一个常数优化(来自洛谷提高组讲义)

for(int i=1;i<=n;i++) //预先算出log_2(i)+1的值，用的时候直接调用就可以了
  lg[i]=lg[i-1]+(1<<lg[i-1]==i);  //看不懂的可以手推一下

接下来就是倍增LCA了，我们先把两个点提到同一高度，再统一开始跳。

但我们在跳的时候不能直接跳到它们的LCA，因为这可能会误判，比如

int lca(int x,int y)
{
if(depth[x]<depth[y]) //用数学语言来说就是：不妨设x的深度 >= y的深度
  swap(x,y);
while(depth[x]>depth[y])
  x=fa[x][lg[depth[x]-depth[y]]-1]; //先跳到同一深度
if(x==y)  //如果x是y的祖先，那他们的LCA肯定就是x了
  return x;
for(int k=lg[depth[x]]-1;k>=0;k--) //不断向上跳（lg就是之前说的常数优化）
  if(fa[x][k]!=fa[y][k])  //因为我们要跳到它们LCA的下面一层，所以它们肯定不相等，如果不相等就跳过去。
    x=fa[x][k], y=fa[y][k];
return fa[x][0];  //返回父节点
}

转自洛谷 MorsLin