树递归编号解决 MEX 子树问题

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

641

树递归编号也挺神奇的，轻松解决一批问题。

零、背景

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