欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LCA

程序员文章站 2022-04-11 10:23:40
...

求LCA(最近公共祖先)的算法有好多,按在线和离线分为在线算法和离线算法。

离线算法有基于搜索的Tarjan算法较优,而在线算法则是基于dp的ST算法较优。

本文讲述ST算法。

这个算法是基于RMQ(区间最大最小值编号)的,而求LCA就是把树通过深搜得到一个序列,然后转化为求区间的最小编号。

比如说给出这样一棵树。

LCA


我们通过深搜可以得到这样一个序列:

节点ver 1 3 1 2 5 7 5 6 5 2 4 2 1 (先右后左)
深度deep 1 2 1 2 3 4 3 4 3 2 3 2 1 
首位first 1 4 2 11 5 8 6 

搜索得到序列之后假如我们想求4 和 7的 LCA

那么我们找4和7在序列中的位置通过first 数组查找发现在6---11

即7 5 6 5 2 4 在上面图上找发现正好是以2为根的子树。而我们只要找到其中一个深度最小的编号就可以了、

这时候我们就用到了RMQ算法。

维护一个dp数组保存其区间深度最小的下标,查找的时候返回就可以了。

比如上面我们找到深度最小的为2点,返回其编号10即可。

这部分不会的可以根据上面链接研究一些RMQ


//ver:节点编号 deep:深度 first:点编号位置 dir:距离
int sz, ver[2 * MX], deep[2 * MX], first[MX], dp[2 * MX][30], vis[MX], dir[MX];
void init(int n) {
    for (int i = 0; i <= n; i++) dir[i]=vis[i] = 0;
    sz = 0;
}
void dfs(int u , int dep) {
    vis[u] = true; ver[++sz] = u;
    first[u] = sz; deep[sz] = dep;
    for (int i = head[u]; ~i ; i = E[i].nxt) {
        if ( vis[E[i].v] ) continue;
        int v = E[i].v;
        dir[v] = dir[u] + E[i].w;
        dfs(v, dep + 1);
        ver[++sz] = u; deep[sz] = dep;
    }
}
void ST(int n) {
    for (int i = 1; i <= n; i++) dp[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int a = dp[i][j - 1] , b = dp[i + (1 << (j - 1))][j - 1];
            dp[i][j] = deep[a] < deep[b] ? a : b;
        }
    }
}
//中间部分是交叉的。
int RMQ(int l, int r) {
    int k = 0;
    while ((1 << (k + 1)) <= r - l + 1) k++;
    int a = dp[l][k], b = dp[r - (1 << k) + 1][k]; //保存的是编号
    return deep[a] < deep[b] ? a : b;
}
int LCA(int u , int v) {
    int x = first[u] , y = first[v];
    if (x > y) swap(x, y);
    int ret = RMQ(x, y);
    return ver[ret];
}
void pre_solve(int n) {
    dir[1] = 1;
    dfs(1, 1);
    ST(sz);
}


相关标签: LCA