RMQ LCA 解决 MEX 子树问题

天空的代码世界 2021-09-16

660

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];
}
复制