LCA 倍增/tarjan/树刨

64次阅读

共计 1990 个字符，预计需要花费 5 分钟才能阅读完成。

$dep[u]$ ：存点 $u$ 的深度
$fa[i][j]$ ：从 $u$ 点往上跳 $2^i$ 层的祖先节点。

例如： $9$ 节点往上跳 $2^0$ 的祖先节点是 $3$ ，跳 $2^1$ 的祖先节点是 $6$ ，跳 $2^2$ 的祖先节点是 $1$ ，跳 $2^3$ 的祖先节点是 $0$

int fa[N][30] ;
int dep[N] ;
vector<int> e[N] ;//存图
void add(int u, int v){
    e[u].push_back(v) ;
}
void dfs(int x,int f){
    dep[x] = dep[f] + 1 ;       
    fa[x][0] = f ;
    for(int i = 1 ; i <= 20 ; ++ i){
        fa[x][i] = fa[fa[x][i-1]][i-1] ;//倍增
    }
    for(auto y : e[x]){
        if(f != y) dfs(y,x) ;
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u,v) ;
    for(int i = 20 ; i >= 0 ; -- i){//贪心让两个点深度相等
        if(dep[fa[u][i]] >= dep[v] ){
            u =  fa[u][i] ;
        }
    }
    if(u == v) return v ;//一个节点是另一个节点的祖先节点
    for(int i = 20 ; i >= 0 ; -- i){//贪心让两个深度相等的点最终上一层的点相等，也可以说是找到深度最低的两个不相等的点。
        if(fa[u][i] != fa[v][i] ){
            u =  fa[u][i] ;
            v =  fa[v][i] ;
        }
    }
    return fa[u][0] ;
}

离线算法，利用并查集维护祖先节点。

维护两个点的公共祖先，我们可以在判断（u,v）的最近公共祖先时，如果其中一个点（u）已经搜索了（st标记为true），在搜索完另一个节点(v)时，另一个节点（u）的祖先节点就是这两个节点的最近公共祖先，因为我们搜索完成一个节点才会添加边，相当于时从下往上，从左往右添加边，所以等到搜索完两个节点时，此时图中的根节点就是两者的公共祖先。

void tarjan(int x){
    st[x] = true ;
    for(auto y : e[x]){
        if(!st[y]){
            tarjan(y) ;
            p[y] = x ;
        }
    }
    for(auto y : query[x]){
        int i = y.second ;
        int v = y.first ;
        if(st[v]) ans[i] = find(v) ;//x节点走完后，v点已经走过（这里的x和v是一组查询），说明最近公共祖先就是现在（现有的边所构成的）图中的v节点祖先节点
    }
}
int s ;
void solve(){
    cin >> n  >> m >> s;
    int u, v ;
    int t = n- 1 ;
    _rep(i,1,n) p[i] = i ;
    while(t--){
        cin >> u >> v ;
        add(u,v) ;
        add(v,u) ;
    } 
    _rep(i,1,m){
        cin >> u >> v ;
        if(u == v){
            ans[i] = u ;
            continue ;
        }
        query[u].push_back({v,i}) ;
        query[v].push_back({u,i}) ;
    }
    tarjan(s) ;
    _rep(i,1,m){
        cout << ans[i] << endl ;
    }
}

重儿子：父节点的所有儿子中，子树结点数目最多的节点。
轻儿子：父节点的所有儿子中，除重儿子以外的儿子。
重边：父节点和儿子连成的边。
重链：由多条重边连接而成的路径。

整棵树会被刨分成若干条重链。
轻儿子一定是每条重链的顶点。
任意一条路径被切分成不超过 $logn$ 条重链。

数组

fa[u]：存u的父节点
dep[u]：存u的深度
son[u]：存u的重儿子
sz[u]：存以u为根的子树节点数
top[u]：存u所在重连的顶点
id[u]：存u刨分后的新编号
nw[cnt]：存新编号在树中所对应节点的权值

算法

dfs1：搞出fa，dep，sz，son

void dfs1(int x, int f){
    dep[x] =dep[f] + 1 ;//深度
    fa[x] = f ;//父节点
    sz[x] = 1 ;
    for(auto e : e[x]){
        if(e == f) continue ;
        dfs1(e,x) ;
        sz[x] += sz[e] ;
        if(sz[son[x]] < sz[e]) son[x] = e;
    }
}

dfs2：搞出top，id，nw

void dfs2(int x,int y){
    top[x] = y ;//记录链头
    if(!son[x]) return ;
    dfs2(son[x],y) ;//搜索重链上的重儿子
    for(auto e : e[x]){
        if(e == fa[x] || e == son[x]) continue ;
        dfs2(e,e) ;//新开一条重链
    }
}

让两个游标沿着各自的重链向上跳，跳到同一条重链上时，深度较小的那个游标所指向的点就是 LCA 。

int lca(int x, int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x,y) ;
        x = fa[top[x]] ;
    }
    return dep[x] < dep[y] ? x : y ;
}

正文完

发表至：图论数据结构

2024-10-29

0