RMQ LCA 解决 MEX 子树问题

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


零、背景

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 很强,你不学习一下?

PS:相关代码上传到 github,点击原文查看代码。

加油,算法人。

《完》

-EOF-

题图:来自朋友圈。

RMQ LCA 解决 MEX 子树问题

上篇文章:树上并查集

推荐:leetcode 第 258 场算法比赛

长按二维码,一起成长学习


RMQ LCA 解决 MEX 子树问题

RMQ LCA 解决 MEX 子树问题

▲ 长按关注,天天成长

觉得有帮助可以点击好看与转发,谢谢!

Click to rate this post!
[Total: 0 Average: 0]

人已赞赏
名家说每日优选

Filecoin plus 目标加码:半年内算力扩大近5 EiB ,生态变局已来!

2021-9-17 0:12:18

DfinityRust开发名家说小白百科每日优选

【Rust 日报】2021-09-16 Pipette: 一个模仿 Elixir 的管道操作的包,没有使用宏

2021-9-17 0:13:27

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
有新消息 消息中心
搜索