递归编号 解决 MEX 子树问题

作者: | 更新日期:

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

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

零、背景

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

比赛的时候我使用贪心,把树转化为链,然后 DFS 通过了。

上上篇文章《树上并查集》介绍了一个万能的树上并查集方法,也解决这个问题,甚至允许有重复权重值。
上上篇文章《RMQ LCA 解决 MEX 子树问题》介绍了一个 LCA 的方法,来解决问题,不过不支持重复权重值。

今天我再分享一个递归编号的算法来解决这个问题。

一、题目

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

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

二、分析

基本思路:对于一个子树的根,我们依次判断一个权重是否在这个子树上,在了答案加1,直到找到答案即可。

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

所以,只有权重为 1 节点到根节点这条链才需要多次判断寻找答案,其他节点一次就可以找到答案。

最坏复杂度:假设输入就是链,且 1 是叶子节点,此时复杂度会退化到 O(n^2)

优化:如果儿子的答案为 x,那么父节点的答案至少为 x。
因此父节点没必要从 1 开始寻找答案,可以取所有儿子答案的最大值开始循环判断。
此时链的复杂度就变成了 O(n)

而且我们可以发现,每当某个节点的答案加 1 的时候,就相当于从树中减去一个点,整个树顶多减去 n 个点。
所以整个树的最坏复杂度是 O(n)

三、节点是否在子树上

上面的分析依赖一个算法:如何快速判断一个 x 节点在一个子树 y 上。

一种方法是求 LCA(x, y),如果最近祖先是 y,则代表在子树上。

更简单的方法是对树进行先序遍历分配编号,并在根上储存子树的编号范围。
这样通过编号比大小就可以知道一个节点是否在一个子树上了。

预处理如下,对于当前的子树根,可以只分配一个编号,也可以分配两个编号,不影响结果。

vector<int> L, R;
int index_num = 0;

void DfsIndex(int x) {
    L[x] = ++index_num;
    for(auto y: g[x]) {
        DfsIndex(y);
    }
    R[x] = ++index_num;
}

分配编号后,就可以先得到儿子们的最大答案,然后继续循环判断是否有更大的答案。

void DfsSolver(int x) {
    for(auto y: g[x]) {
        DfsSolver(y);
        ans[x] = max(ans[x], ans[y]); // 子树的最大答案
    }
    while(rnums[ans[x]] != -1) {
        int y = rnums[ans[x]];
        if(L[x] <= L[y] && R[y] <= R[x]) { // y 在 x 为根的子树内
            ans[x]++;
        }else {
            break;
        }
    }
}

四、最后

由于权重值互不相同,这道题竟然还可以通过递归分配编号,然后通过比大小来做。

不过这里循环找答案的地方有点反直觉,很容易以为会超时。
但是一番证明后,会发现不会超时,顶多判断 O(n) 次。

你当时是否有想到这个方法呢?

《完》

-EOF-

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

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

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

tiankonguse +
穿越