模板 LCA

Varuxn · 2021-06-30 18:58:43 · 个人记录

\huge Luogu日报

各类LCA板子

以下n表示节点数，m表示询问次数

建边，以及读入

struct Edge
{
    int tot,head[N],nxt[M],ver[M];
    void add(int x,int y)
    {
        ver[++tot]=y;
        nxt[tot]=head[x];
        head[x]=tot;
    }
}e;
for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        e.add(x,y);
        e.add(y,x);
    }

Tarjan

离线算法

时间复杂度：\mathcal{O(n+m)}

初始化：

for(int i=1,x,y;i<=m;i++)
{
    scanf("%d%d",&x,&y);
    if(x==y)
        lca[i]=0;
    else
    {
        lca[i]=INF;
        v[x].push_back(make_pair(i,y));
    }
}
LCA(1);

求LCA

void LCA(int x,int fat)
{
    vis[x]=1;
    for(int i=e.head[x];i;i=e.next[i])
    {
        int to=e.ver[i];
        if(to==fat||vis[to])
            continue;
        LCA(to,x);
        fa[to]=x;
    }
    for(int i=0;i<v[x].size();i++)
    {
        int id=v[x][i].first,to=v[x][i].second;
        if(vis[to]!=2)
            continue;
        lca[id]=find(to);
    }
    vis[x]=2;
}

倍增

在线算法

预处理时间复杂度：\mathcal{O(nlog(n))}

查询时间复杂度：\mathcal{O(log(n))}

空间复杂度：\mathcal{O(nlog(n))}

初始化

void dfs(int x,int fa)
{
    dfn[x]=++tim;
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    for(int i=0;f[x][i];i++)
        f[x][i+1]=f[f[x][i]][i];
    for(int i=e1.head[x];i;i=e1.nxt[i])
        if(e1.ver[i]!=fa)
            dfs(e1.ver[i],x);
}

求LCA

int LCA(int x,int y)
{
    if(x==y)
        return x;
    if(dep[x]>dep[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[f[y][i]]>=dep[x])
            y=f[y][i];
    if(x==y)
        return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}

RMQ

在线算法

设T=2 \times n−1

时间复杂度：

预处理：\mathcal{O(TlogT)}

查询：\mathcal{O}(1)

初始化

inline void dfs(int x,int fa)
{
    dfn[x]=++tim;
    dep[x]=dep[fa]+1;
    id[tim][0]=x;
    for(int i=e1.head[x];i;i=e1.nxt[i])
        if(e1.ver[i]!=fa)
        {
            dfs(e1.ver[i],x);
            id[++tim][0]=x;
        }
}
inline void RMQ_init()
{
    for(int i=2;i<=tim;i++)
        lg[i]=lg[i>>1]+1;
    for(int j=1;j<=20;j++)
        for(int i=1;(i+(1<<j)-1)<=tim;i++)
        {
            int num=i+(1<<(j-1));
            id[i][j]=(dep[id[i][j-1]]<dep[id[num][j-1]])?id[i][j-1]:id[num][j-1];
        }
}

求LCA

inline int LCA(int x,int y)
{
    x=dfn[x],y=dfn[y];
    if(x>y)
        swap(x,y);
    int k=lg[y-x+1];
    return (dep[id[x][k]]<dep[id[y-(1<<k)+1][k]])?id[x][k]:id[y-(1<<k)+1][k];
}

树链剖分

初始化

void pre_dfs(int x)
{
    size[x]=1;
    for(int i=e1.head[x];i;i=e1.nxt[i])
    {
        int to=e1.ver[i];
        if(!size[to])
        {
            f[to]=x;
            dep[to]=dep[x]+1;
            pre_dfs(to);
            size[x]+=size[to];
            if(size[son[x]]<size[to])
                son[x]=to;
        }
    }
}
void pre_dfs(int x,int tp)
{
    topp[x]=tp;
    dfn[x]=++tim;
    id[tim]=x;
    if(son[x])
        pre_dfs(son[x],tp);
    for(int i=e1.head[x];i;i=e1.nxt[i])
        if(!dfn[e1.ver[i]])
            pre_dfs(e1.ver[i],e1.ver[i]);
}

求LCA

int LCA(int x,int y)
{
    while(topp[x]^topp[y])
    {
        if(dep[topp[x]]<dep[topp[y]])
            swap(x,y);
        x=f[topp[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    return x;
}