WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Least Common Ancestors 算法总结
Least Common Ancestors 算法总结

RMQ求LCA

复杂度:O(nLogn)预处理, O(1)询问。

处理出树的DFS序,那么一棵子树就转化成为了DFS序列上的一个区间。求LCA,就变成了求序列上对应的点中Dep最小的编号,于是LCA问题就转化成为了区间RMQ问题。

namespace LCA{
    const int MAXN=4e5+50;
    const int LOGN=25;
    int dep[MAXN], ver[MAXN*2], rev[MAXN], dfn;
    int Pow2[LOGN], Log2[MAXN*2];
    struct Edge{
        int v, nxt;
        Edge(){}
        Edge(int v0, int n0){ v=v0; nxt=n0; }
    }e[MAXN*2];
    int head[MAXN], nume;

    /**
     * DFS For LCA
     */
    void dfs(int x, int from){
        dep[x]=dep[from]+1;
        ver[++dfn]=x; rev[x]=dfn;
        for (int i=head[x]; i; i=e[i].nxt){
            int v=e[i].v; if (v==from) continue;
            dfs(v, x); ver[++dfn]=x;
        }
    }

    /**
     * RMQ For LCA
     */
    int dp[MAXN*2][LOGN];
    void st(){
        for (int i=1; i<=dfn; i++) dp[i][0]=ver[i];
        for (int k=1; k<LOGN; k++){
            for (int i=1; i+Pow2[k]-1<=dfn; i++){
                int x=dp[i][k-1], y=dp[i+Pow2[k-1]][k-1];
                dp[i][k]=dep[x]<dep[y]?x:y;
            }
        }
    }
    int rmq(int left, int right){
        int k=Log2[right-left+1];
        int x=dp[left][k], y=dp[right-Pow2[k]+1][k];
        return dep[x]<dep[y]?x:y;
    }

    /**
     * Init Log2 And Pow2
     */
    inline void init(){
        Log2[0]=-1; for (int i=1; i<MAXN*2; i++) Log2[i]=Log2[i>>1]+1;
        Pow2[0]=1; for (int i=1; i<LOGN; i++) Pow2[i]=Pow2[i-1]<<1;
    }

    /**
     * Init Edges
     */
    inline void initEdge(){ memset(head, 0, sizeof(head)); nume=0; }

    /**
     * Add Edges
     */
    inline void addEdge(int u, int v){
        e[++nume]=Edge(v, head[u]);
        head[u]=nume;
        e[++nume]=Edge(u, head[v]);
        head[v]=nume;
    }

    /**
     * Prepare LCA
     */
    inline void prepare(){ dep[0]=dfn=0; dfs(1, 0); st();}

    /**
     * Query LCA
     */
    inline int query(int u, int v){
        int x=rev[u], y=rev[v];
        if (x>y) swap(x, y);
        return rmq(x, y);
    }
}

倍增求LCA

复杂度:O(nLogn)预处理,O(Logn)询问。
预处理出一个节点向上跳2^k步之后能够到达哪个节点,然后使用求出两个节点向上跳的第一次相遇位置,即为LCA。

namespace LCA{
    const int MAXN=4e5+50;
    const int LOGN=25;
    int dep[MAXN], fa[MAXN][LOGN];
    struct Edge{
        int v, nxt;
        Edge(){}
        Edge(int v0, int n0){ v=v0; nxt=n0; }
    }e[MAXN*2];
    int head[MAXN], nume;

    /**
     * Init For LCA
     */
    inline void initEdge() { memset(head, 0, sizeof(head)); nume=0; }

    /**
     * Add Edges
     */
    inline void addEdge(int u, int v){
        e[++nume]=Edge(v, head[u]);
        head[u]=nume;
        e[++nume]=Edge(u, head[v]);
        head[v]=nume;
    }

    /**
     * DFS For LCA
     */
    void dfs(int x, int from){
        dep[x]=dep[fa[x][0]=from]+1;
        for (int i=1; i<LOGN; i++) fa[x][i]=fa[fa[x][i-1]][i-1];
        for (int i=head[x]; i; i=e[i].nxt){
            int v=e[i].v; if (v==from) continue;
            dfs(v, x);
        }
    }

    /**
     * Prepare For LCA
     */
    inline void prepare(){ dep[1]=0; dfs(1, 1); }

    /**
     * Query For LCA
     */
    inline void swim(int &x, int h){ for (int i=0; i<LOGN; i++, h/=2) if (h&1) x=fa[x][i]; }
    int query(int x, int y){
        if (dep[x]<dep[y]) swap(x, y);
        swim(x, dep[x]-dep[y]);
        if (x==y) return x;
        for (int i=LOGN-1; i>=0; i--){
            if (fa[x][i]==fa[y][i]) continue;
            x=fa[x][i]; y=fa[y][i];
        }
        return fa[x][0];
    }
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

发表评论

textsms
account_circle
email

WNJXYKのBlog

Least Common Ancestors 算法总结
RMQ求LCA 复杂度:$O(nLogn)$预处理, $O(1)$询问。 处理出树的DFS序,那么一棵子树就转化成为了DFS序列上的一个区间。求LCA,就变成了求序列上对应的点中Dep最小的编号,于是LCA问题就…
扫描二维码继续阅读
2018-09-26
<--! http2https -->