前言

LCA的求法有多重多样,总结下来是下面这4种.希望大家可以加油!

暴力求LCA

我们考虑dfs求出每一个点的父亲(在当前根下),然后直接先暴力跳到同一个深度,再同时跳

void dfs(int u,int f){    fa[u]=f;dep[u]=dep[f]+1;    for(re int i=front[u];i;i=e[i].nxt){        int v=e[i].to;        if(v==f)continue;        dfs(v,u);    }}int lca(int u,int v){    if(dep[u]

倍增求LCA

我们考虑每一次跳1个父亲的速度太慢,那么怎么优化呢?

这个时候就需要用到倍增这种思想了.

没有学过倍增的同学可以先写一下ST表,可能会对倍增有比较深刻的理解.

我们假设这样子一个变量\(f[i][j]\)表示点\(i\)的第\(2^j\)个父亲是哪个节点.

因为每一个数都可以二进制表示,所以我们考虑每一次从大到小枚举跳的东西,然后就可以做到\(\Theta(n\ log(n))\)

void dfs(int u,int fa){    dep[u]=dep[fa]+1;    for(re int i=front[u];i;i=nxt[i]){        int v=to[i];        if(v!=fa)dfs(v,u),f[0][v]=u;    }}int lca(int a,int b){    if(dep[a]
    
     =dep[b])            a=f[i][a];    if(a==b)return a;    for(re int i=20;~i;i--)        if(f[i][a]!=f[i][b])            a=f[i][a],b=f[i][b];    return f[0][a];}
    

树链剖分求LCA

考虑把一个树分成轻链与重链,然后直接跳链就好了.

void dfs1(int u,int f){    fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;    for(re int i=front[u];i;i=e[i].nxt){        int v=e[i].to;        if(v==fa[u])continue;        dfs1(v,u);        siz[u]+=siz[v];        if(siz[v]>siz[son[u]])son[u]=v;    }}void dfs2(int u,int tp){    top[u]=tp;    if(!son[u])return;    dfs2(son[u],tp);    for(re int i=front[u];i;i=e[i].nxt){        int v=e[i].to;        if(v==fa[u] || v==son[u])continue;        dfs2(v,v);    }}void swap(int &a,int &b){    int tmp=a;a=b;b=tmp;}int lca(int u,int v){    while(top[u]!=top[v]){        if(dep[top[u]]
    
     dep[v]?v:u;}
    

Tarjan求LCA

考虑把每一个询问当做一条边处理,那么如果这两个都被访问了,显然另一个点的祖先一定是他们的LCA.

所以可以很容易地写出这一段代码.(注意最后合并)

int find(int x){    if(f[x]!=x)f[x]=find(f[x]);    return f[x];}void Add(int u,int v){    to[++cnt]=v;nxt[cnt]=front[u];    front[u]=cnt;}void Addques(int u,int v,int Id){    toq[++cnt]=v;    id[cnt]=Id;nxtq[cnt]=frontq[u];    frontq[u]=cnt;}void dfs(int u,int fa){    b[u]=1;    for(int i=front[u];i;i=nxt[i]){        int v=to[i];        if(v!=fa){            dfs(v,u);            for(int j=frontq[v];j;j=nxtq[j]){                int vv=toq[j];                if(b[vv])ans[id[j]]=find(vv);            }            int uu=find(u),vv=find(v);            if(uu!=vv)f[vv]=uu;        }    }}