RMQ LCA 解决 MEX 子树问题

作者: | 更新日期:

LCA 算法学会了,又可以解决一批问题。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

leetcode 第 258 场算法比赛》的第四题是一道很有趣的题。

比赛的时候我使用贪心,把树转化为链,然后 DFS 通过了。
上篇文章《树上并查集》介绍了一个万能的树上并查集方法,也解决这个问题,甚至允许有重复权重值。

今天我再分享一个 LCA 算法来解决这个问题。

一、题目

给一个有根树,每个节点有一个正整数值(互不相同)。
对于每个子树,问子树的节点值里面,最小的未出现的正整数是多少。

最小的未出现的正整数有个专业名称,叫做 mex(Minimum excludant)。

二、分析

对于子树节点没 1 的子树根,答案肯定都是 1。
所以权重为 1 的节点到根节点的值不确定外,其他节点的答案肯定都是 1。

那权重为 1 的节点到根节点的答案如何计算呢?

比赛的时候,我是从下到上 DFS 解决的。

这里我们换一个思路看看待问题。

假设权重为 1 的节点为 u,权重为 2 的节点为 v, 我们可以求两个节点的 LCA(u, v),不妨假设为 nxt

对于 nxt 有两种情况。

第一种情况:v(2)u(1) 的子树上,此时 nxt 等于 u。 可以确定,u 到根路径上的点的答案至少都是 3,因为 1 和 2 都在子树上。

第二种情况:v(2) 不在 u(1) 的子树上,此时 nxt 是 u 和 v 的祖先点。
可以确定,u 到 nxt 这个路径上,除了 nxt,其他的点答案肯定是 2,因为权重 2 在其他子树上。

进行一轮这样的操作,路径上一些点的答案可以从下到上确定若干个。

之后用相同的方法,找到答案确定是 3 的,答案确定是 4 的,依次递推,找到答案为 n 的结束。

复杂度:O(n log(n))

三、RMQ 与 LCA

对于 最近公共祖先 LCA,最朴素的方法是暴力方法查询。

假设预处理求出所有点的高度了。
可以先使得两个点处于相同的高度,然后两个节点不断判断父节点是否相同,不同则同时上升高度。

暴力方法的平均复杂度O(log(n)),最坏复杂度O(n)

面对这个复杂度,就需要去想办法优化了。
比如可以去想,上移的时候,能不能加速移动。

如果一次可以移动 2 次,那一下就节省一半时间。
所以我们可以利用二分的思想,预处理计算出移动指数次的父节点是谁。

对于上升对齐高度,可以使用二进制思想,快速对齐高度。
高度对齐后,再使用指数快速衰减的性质,快速找到第一个公共祖先。

复杂度:O(log(n))

初始化代码如下,关键的两行代码写了注释:

const int maxn = 100005;
const int maxn_log = 20;
vector<int> g[maxn];
int f[maxn][maxn_log], dep[maxn];

void DfsRMQ(int u){
    for(int v: g[u]) {
        // 初始化:第 2^0 = 1 个祖先就是它的父亲节点,dep 也比父亲节点多 1。
        dep[v] = dep[u] + 1;
        f[v][0] = u; 

        // 初始化:其他的祖先节点:第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第 2^(i-1) 的祖先节点。
        for(int i = 1; i < maxn_log; i++) {
            f[v][i] = f[f[v][i-1]][i-1];
        }
        DfsRMQ(v);
    }
}

查询 LCA 代码如下,先对齐高度,再快速上移。

int Lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int d = dep[u] - dep[v], i = maxn_log - 1; d && i >= 0; i--) {
        if(d & (1<<i)) {
            u = f[u][i];
            d = d ^ (1<<i);
        }
    }

    if(u == v) return u;

    for(int i = maxn_log - 1; i >= 0; i--) {
        if(f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

关于对齐高度以及公共祖先上移的几何含义,其实都是二进制思想。
对齐高度由于知道二进制数字,所以直接找位数,快速上移即可。
公共祖先,由于不知道二进制数字,只能从大到小一次判断,但也是 log(n)级别的。

四、最后

RMQ 果然是一个有趣的算法,利用倍增的思想,将线性问题转化为了log问题。

RMQ 很强,你不学习一下?

加油,算法人。

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
公众号ID:tiankonguse-code

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

关注公众号,接收最新消息

tiankonguse +
穿越