Chlience

【算法】LCA 转 RMQ 问题
$LCA$ 问题,即一类树上最近公共祖先问题这个东西有很多种不同的方法来实现,比如说:树链剖分,倍增,$Tarja...
扫描右侧二维码阅读全文
03
2019/01

【算法】LCA 转 RMQ 问题

$LCA$ 问题,即一类树上最近公共祖先问题
这个东西有很多种不同的方法来实现,比如说:树链剖分,倍增,$Tarjan$ 算法

它们各自有各自的优点,比如说容易打啊,常数小啊,装逼啊,等等

在这里介绍一种预处理 $O(n\log n)$,查询 $O(1)$ 的在线算法,也就是将 $LCA$ 转化为 $RMQ$ 问题,用 $ST$ 表来解决

如何转化

首先对树进行一遍 $DFS$,并将访问顺序记录下来,注意不仅仅要记录进入的顺序,回溯时也需要记录

LCA-RMQ.png

对于这样一棵简单的二叉树,其访问顺序如下:

访问时间123456789
访问节点123252141

发现每个节点都出现了 子树个数$+1$ 次,这是由于每次从子树回溯都会重新访问一遍当前节点,表示当前子树访问完毕

那么两个节点首次访问的时间之间必然会出现其 $LCA$ 节点(因为遇到一个点后想要访问另外一个节点必然要回退到 $LCA$ 位置)

同样,并不会出现比 $LCA$ 深度更小的节点,因为其回溯到深度更小节点便说明该子树访问完毕,但是并没有访问到另外一个节点,说明该节点不是两者的 $LCA$

所以说,在维护询问时间和询问节点时同时保存节点深度,在两点第一次出现的时间之间深度最小的节点即为两者 $LCA$

访问时间123456789
访问节点123252141
深度123232121

比如说点对 $(4,5)$ ,其首次出现时间分别为 $5,8$,那么 $5,8$ 之间深度最小的点为 $1$ 号点,深度为 $1$,所以说 $LCA(4,5)=1$

也就是说,我们通过记录这样几个量,实现了将 $LCA$ 问题转化为 $RMQ$ 问题,接下来只需要用 $ST$ 表维护 时间-深度 表即可

由于每个点被加入到数列中的次数和子树大小相关,每个点作为儿子使得它的父亲多在数列中出现一次,所以数列总长度为 $2n$,预处理复杂度为 $O(n \log n)$,询问复杂度为 $O(1)$,问题圆满解决

Code

建议先思考再看代码,这个并不难,靠自己肯定能 $yy$ 出来的

#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int bintwo[22] , logtwo[N << 1];
int dep[N] , fst[N] , DFN;
int n , m , s;
int f[N << 1][22];

struct Edge {
    int t , n;
    void add(int _t , int _n) {t = _t; n = _n;}
}e[N << 1];
int head[N] , tot;

void addedge(int u , int v) {
    e[++ tot].add(v , head[u]);
    head[u] = tot;
}

void prepare() {
    bintwo[0] = 1;
    for(int i = 1 ; i <= 20 ; ++ i)
        bintwo[i] = bintwo[i - 1] << 1;
    logtwo[0] = - 1;
    for(int i = 1 ; i <= 1000000 ; ++ i)
        logtwo[i] = logtwo[i / 2] + 1;

    for(int j = 1 ; j <= logtwo[n << 1] ; ++ j)
        for(int i = 1 ; i + bintwo[j] - 1 <= (n << 1) ; ++ i) 
            f[i][j] = dep[f[i][j - 1]] < dep[f[i + bintwo[j - 1]][j - 1]] ? f[i][j - 1] : f[i + bintwo[j - 1]][j - 1];
}
void dfs(int x , int deep) {
    fst[x] = ++ DFN; dep[x] = deep;
    f[DFN][0] = x;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(fst[e[i].t]) continue;
        dfs(e[i].t , deep + 1);
        ++ DFN;
        f[DFN][0] = x;
    }
}
int query(int a , int b) {
    a = fst[a]; b = fst[b];
    if(a > b) swap(a , b);
    int len = logtwo[b - a + 1];
    return dep[f[a][len]] < dep[f[b - bintwo[len] + 1][len]] ? f[a][len] : f[b - bintwo[len] + 1][len];
}

int main() {
    n = read(); m = read(); s = read();
    for(int i = 1 ; i < n ; ++ i) {
        int u = read() , v = read();
        addedge(u , v); addedge(v , u);
    }
    dfs(s , 1);
    prepare();
    for(int i = 1 ; i <= m ; ++ i) {
        int u = read() , v = read();
        printf("%d\n" , query(u , v));
    }
    return 0;
}
Last modification:January 3rd, 2019 at 08:37 pm

Leave a Comment