使用欧拉序 st 表 O(1) 求 LCA

欧拉序

~~一开始是从某篇题解里看到的~~，后来百度了一下就会了（

这是一种预处理

什么是欧拉序

举个例子，下面是一棵树：

上面有

将整个

这就是欧拉序了。

如何求出答案

如何求

假设我们要求

那我们先把欧拉序中

1 → 2 → 4 → 7 → 4 → 8 → 4 → 2 → 5 → 2 → 1 → 3 → 6 → 3 → 1

暴力找一遍

由于欧拉序不变，此时可以用 $\text{st}st 表的方法优化，就能 O(1)O(1) 查询。$

设 $2^j 个点中深度最小的点。$

#define N 1000007
int n,m,rt;
struct edge{
    int to,nxt;
}e[N<<1];
int tot,head[N];
inline void adde(int u,int v){
    e[++tot]=(edge){v,head[u]};
    head[u]=tot;
}

int dep[N],lg[N<<1],f[N<<1][21];
int dfn[N<<1],que[N<<1],idx;
void dfs(int u,int pa)
{
    dfn[u]=++idx,que[idx]=u;
    dep[u]=dep[pa]+1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==pa)continue;
        dfs(v,u);
        que[++idx]=u;
    }
}

建

void buildst()
{
    For(i,1,idx)f[i][0]=que[i];
    For(j,1,20)
        for(int i=1;i+(1<<j)<=idx;++i){
            int f1=f[i][j-1],f2=f[i+(1<<j-1)][j-1];
            f[i][j]=dep[f1]<dep[f2]?f1:f2;
        }
    lg[0]=-1;
    For(i,1,idx)lg[i]=lg[i>>1]+1;
}

查询：

inline int getlca(int u,int v)
{
    if(dfn[u]>dfn[v])swap(u,v);
    u=dfn[u],v=dfn[v];
    int kk=lg[v-u+1],f1=f[u][kk],f2=f[v-(1<<kk)+1][kk];
    return dep[f1]<dep[f2]?f1:f2;
}