最近公共祖先 了解+模闆

文章目錄

• 倍增算法 線上更新
• 線上DFS + ST表
• 離線 Tarjan 算法

先附上一個講解非常詳細的部落格

倍增算法 線上更新

class lca_Doubling{ 
public:
    static const int MAXDepth = 20;
    static const int MAXN = 1e5+10;
    static const int MAXM = 3e5+10; // 有向圖雙倍加邊
    struct EDGE {
        int v, w, to;
    }e[MAXM];
    int head[MAXM], cnt = 0; int dis[MAXN];/*dis */
    inline void add ( int u, int v, int w ) {
        e[cnt].v = v, e[cnt].w = w, e[cnt].to = head[u]; head[u] = cnt++;
    }
    int up[MAXN][MAXDepth], deep[MAXN]; 
    int n;
    lca_Doubling( ) { };
    lca_Doubling( int _n ) : n(_n) { };
    void ini_graph ( ) {
        cnt = 0; 
        memset ( head, -1, sizeof ( head ) ); 
/*dis */memset ( dis, 0, sizeof ( dis ) );
		memset ( up, 0, sizeof ( up ) );
		memset ( deep, 0, sizeof ( deep ) );
    }
    inline void ini ( int n ) { 
        this->n = n;
        dfs( 1 ); // 開始搜尋
        up_ini( n ); // 開始預處理
    }
private:
    void dfs ( int u ) { // 搜尋一遍, 記錄所有節點的 深度, 距離, 父節點
        for ( int k = head[u]; k != -1; k = e[k].to ) {
            int v = e[k].v;
            if ( v==up[u][0] ) continue;
            deep[v] = deep[u]+1;
/*dis */    dis[v] = dis[u]+e[k].w;
            up[v][0] = u;
            dfs( v );
        }
    }
    void up_ini ( int n ) { // 預處理倍增數組
        for ( int j = 1; (1<<j) <= n; ++j )
            for ( int i = 1; i <= n; ++i )
                up[i][j] = up[up[i][j-1]][j-1];
    }
public:
    int getAncestor ( int u, int v ) { // 查找最近公共祖先
        if ( deep[u]<deep[v] ) swap( u, v );
        int d = deep[u]-deep[v];
        for ( int i = 0; i < MAXDepth; ++i )
            if ( (1<<i)&d )
                u = up[u][i];
        if ( u == v ) return u;
        for ( int i = MAXDepth-1; i >= 0; --i ) {
            if ( up[u][i] != up[v][i] ) {
                u = up[u][i]; v = up[v][i];
            }
        }
        return up[u][0];
    }
    inline int getDistance ( int u, int v ) { 
        return dis[u]+dis[v]-2*dis[getAncestor(u,v)];
    }
}lca;
           

線上DFS + ST表

離線 Tarjan 算法