LCA

· · 个人记录

双点 LCA

一、欧拉序算法

欧拉序指的是对数进行遍历时依次访问节点的编号排列得到的数列。那么，两个节点的 lca 一定夹在数列中两节点编号之间。

如树是这样的：

           1
     2            3
   4   5       6     7
             8     9   10

欧拉序就为：

1 2 4 2 5 2 1 3 6 8 6 3 7 9 7 10 7 3 1

此时要求7和8的 lca,那么其 lca 就在8 6 3 7间。此时深度最小节点的编号3即为答案。求深度最小的时候需要 RMQ。

二、倍增算法

此算法较为熟知，不详细介绍，详见代码。

#define re register
#define in inline
#define maxn 600005
using namespace std;
int lext[maxn],first[maxn],to[maxn],f[maxn][35],tot=0,dep[maxn],d[maxn],n,candy[maxn],ans=0,more[maxn];
in void add(int x,int y){
    tot++;
    lext[tot]=first[x];
    first[x]=tot;
    to[tot]=y;  
}
in void ad(int x,int y){
    add(x,y);
    add(y,x);
}
in void pre(int u,int father){
    dep[u]=dep[father]+1;
    for(int i=0;i<30;i++) f[u][i+1]=f[f[u][i]][i];
    for(int i=first[u];i;i=lext[i]){
        int v=to[i];
        if(v==father) continue;
        f[v][0]=u;
        pre(v,u);
    }
}
in int ancestor(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=30;i>=0;i--)
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=30;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

多点 LCA

多点LCA可以用分别倍增求 lca 来求解，也可用欧拉序来求（找到这些节点编号在欧拉序中的顺序，lca 编号必在这些编号第一个和最后一个之间，并且是在这之间深度最小的那个）。