一道题，四种做法，N个知识点：mex、dfs序、主席树、启发式合并...

Piper蛋窝

发布于 2021-10-09 11:21:17

6640

发布于 2021-10-09 11:21:17

文章被收录于专栏：Piper蛋窝Piper蛋窝

原题链接：力扣 - 每棵子树内缺失的最小基因值[1]

解释一下什么是 mex 值：

mex(S) 的值为集合 S 中没有出现过的最小自然数。例如，mex({1,2}) = 0、mex({0,1,2,3}) = 4

题目

有一棵根节点为 0 的家族树，总共包含 n 个节点，节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents ，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1 。

总共有

10^5

个基因值，每个基因值都用闭区间 [1,

10^5

] 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是节点 i 的基因值，且基因值互不相同。

请你返回一个数组 ans ，长度为 n ，其中 ans[i] 是以节点 i 为根的子树内缺失的最小基因值。

节点 x 为根的子树包含节点 x 和它所有的后代节点。

示例 1：

输入：parents = [-1,0,0,2], nums = [1,2,3,4]
输出：[5,1,1,1]
解释：每个子树答案计算结果如下：
- 0：子树包含节点 [0,1,2,3] ，基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。
- 1：子树只包含节点 1 ，基因值为 2 。1 是缺失的最小基因值。
- 2：子树包含节点 [2,3] ，基因值分别为 [3,4] 。1 是缺失的最小基因值。
- 3：子树只包含节点 3 ，基因值为 4 。1是缺失的最小基因值。

示例 2：

输入：parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
输出：[7,1,1,4,2,1]
解释：每个子树答案计算结果如下：
- 0：子树内包含节点 [0,1,2,3,4,5] ，基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。
- 1：子树内包含节点 [1,2] ，基因值分别为 [4,6] 。1 是缺失的最小基因值。
- 2：子树内只包含节点 2 ，基因值为 6 。1 是缺失的最小基因值。
- 3：子树内包含节点 [3,4,5] ，基因值分别为 [2,1,3] 。4 是缺失的最小基因值。
- 4：子树内只包含节点 4 ，基因值为 1 。2 是缺失的最小基因值。
- 5：子树内只包含节点 5 ，基因值为 3 。1 是缺失的最小基因值。

示例 3：

输入：parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
输出：[1,1,1,1,1,1,1]
解释：所有子树都缺失基因值 1 。

提示：

n == parents.length == nums.length
2 <= n <=

10^5

对于 i != 0 ，满足 0 <= parents[i] <= n - 1
parents[0] == -1
parents 表示一棵合法的树。
1 <= nums[i] <=

10^5

nums[i] 互不相同。

思路一：集合mex值/dfs分析

这里主要参考了大佬的分析[2]：

既然自底向上更新涉及到大量的集合合并操作，自顶向下更新是不是就会避免这个问题呢？答案是肯定的（至少对于这道题来说是的）。

那么现在考虑自顶向下的更新方式，为了更快的查找最小未出现的数字，初始化一个集合notExist，存放的是整棵树中未出现的数字，那么每次遍历到一个节点时，只需要返回这个集合中的最小值，然后将该节点的值加入集合中。

初始化方式如下：

unordered_set<int> exist;
set<int> notExist;
int mx;
for(int x: nums) {
    mx = max(mx, x);
    exist.insert(x);
}
for(int i = 1; i <= mx+1; ++i) { //最大为mx+1
    if(!exist.count(i)) {
        notExist.insert(i);
    }
}

但是这样会出现一个问题，左右子树的更新顺序会影响其答案的正确性，比如先更新左子树，那么右子树中的节点值尚未加入集合notExist中，那么左子树中节点的mex值可能就是错误的。如果该节点的mex值比其他未加入集合notExist中的值都小，那么该值是正确的，反之该值应该为未加入集合中的那些值中的最小值。现在考虑一个节点的右子树中节点的正确性，由于右子树更新时，左子树中的节点已经加入了集合notExist中，那么右子树的根节点的答案肯定是正确的。

所以提出了这样一个设想，分别独立跑两次先序遍历，一次先更新左子树，一次先更新右子树，然后将两次结果取较小值即为答案。因为这样能保证对每个节点的mex值来说，总有一次的值是正确的，而正确的那个总是两者中较小的那个。

class Solution {
    int n;
    vector<int> res;
    set<int> notExist1, notExist2;  // 注意这里 set 是有序的
    vector<vector<int>> tree;
public:
    //根左右遍历
    void dfs1(int cur, vector<int>& nums) {  // cur 是根，代表一棵子树
        res[cur] = min(res[cur], *notExist1.begin());  // 求 mex ，即 当前子树已有答案 与 左遍历下不存在集合最小值 的最小值
        notExist1.insert(nums[cur]);  // 往下走，相当于抠去了这个节点的值，因此 insert 到 左遍历下不存在集合 里
        for(int v : tree[cur]) {
            dfs1(v, nums);
        }
    }
    //根右左遍历
    void dfs2(int cur, vector<int>& nums) {
        res[cur] = min(res[cur], *notExist2.begin());
        notExist2.insert(nums[cur]);
        for(int i = (int)tree[cur].size() - 1; i >= 0; --i) {
            int v = tree[cur][i];
            dfs2(v, nums);
        }
    }
    vector<int> smallestMissingValueSubtree(vector<int>& fa, vector<int>& nums) {
        n = fa.size();
        res.resize(n, 1e6);
        tree = vector<vector<int>> (n);
        for(int i = 0; i < n; ++i) {
            if(fa[i] >= 0) {
                tree[fa[i]].emplace_back(i);  // 为了自顶向下，建立 {父节点: [子节点集合]} 映射
            }
        }
        unordered_set<int> exist;
        int mx = 0;
        for(int x : nums) {
            mx = max(mx, x);
            exist.insert(x);
        }
        notExist1.clear();
        notExist2.clear();
        for(int i = 1; i <= mx + 1; ++i) {
            if(!exist.count(i)) {
                notExist1.insert(i);
                notExist2.insert(i);
            }  // 现在 notExist1 和 notExist2 里是整棵树的未出现过的数
        }
        dfs1(0, nums);
        dfs2(0, nums);
        return res;
    }
};

时间复杂度：

O(nlogM)

空间复杂度：

O(M)

注：

为数值的最大值

思路二：dfs序/主席树

主要参考大佬的视频[3]：

咱首先看一看啥是 dfs 序：

如上，每个节点多了两个属性：(i: 在dfs中被第几次遍历到的, j: 在dfs中被遍历到了，且没有子树继续探索了) ，如果该点是叶子节点，则 j 等于 i ，如果该点不是叶子节点，则 j 为自己最后一个子节点的 j 。

dfs 序则有一个很神奇的性质：

如上，我们给每个节点按照 i 排序，如果我们想访问以节点 2 （dfs序为(3, 4)）为根的子树，我们只需要遍历dfs序i处于区间[3, 4]的节点们就好了。

如上，我们就把子树集合变为了区间表达。

对于本题，如上，依着 dfs 序建立主席树，每棵主席树维护的是基因值的 [1, 1e5] 的区间。假设我们现在想知道节点 2 （dfs序为(3, 4)）的基因信息，则我们用主席树 4 减去主席树 2 得到 [3, 4] 的基因信息，然后求和（看是否连续），再二分看 mex 值就行了。（这里主席树没太看懂，系统学到再说吧）

const int MAXN = 1e5 + 50;
vector<int> edge[MAXN];  // 树结构
int iDfs[MAXN], oDfs[MAXN], dfn, rDfs[MAXN];  // dfs 序
int root[MAXN];  // 主席树

void dfs(int x, int father){
    iDfs[x] = ++dfn; rDfs[dfn] = x;  // rDfs 是反查， reverse dfs 表示 dfs 序对应哪个节点
    for (int v: edge[x]) dfs(v, x);
    oDfs[x] = dfn;  // 子节点遍历完了，离开时， dfs 序是多少，记录下来
}

struct BTree{
    int ch[2], sum;
}tree[MAXN * 100];
int numn;

void init(int x, int prev){
    tree[x].ch[0] = tree[prev].ch[0];
    tree[x].ch[1] = tree[prev].ch[1];
    tree[x].sum = tree[prev].sum;
}


void insert(int& x, int y, int left, int right, int v){
    x = ++numn;
    tree[x].ch[0] = tree[y].ch[0];
    tree[x].ch[1] = tree[y].ch[1];
    tree[x].sum = tree[y].sum + 1;
    
    if (left == right) return;
    
    int mid = (left + right) / 2;
    if (v <= mid) 
        insert(tree[x].ch[0], tree[y].ch[0], left, mid, v);
    else{
        insert(tree[x].ch[1], tree[y].ch[1], mid + 1, right, v);
    }
}

int query(int x, int y, int left, int right, int l, int r){
    if (x == 0 && y == 0) return 0;
    if (l <= left && right <= r){
        int ret = 0;
        if (x != 0) ret = tree[x].sum;
        if (y != 0) ret -= tree[y].sum;
        return ret;
    }else{
        int mid = (left + right) / 2;
        int ret = 0;
        if (l <= mid) ret += query(tree[x].ch[0], tree[y].ch[0], left, mid, l ,r);
        if (mid + 1 <= r) ret += query(tree[x].ch[1], tree[y].ch[1], mid + 1, right, l, r);
        return ret;
    }
}

class Solution {
public:
    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
        int n = parents.size();
        for (int i = 0; i <= n; i++) edge[i].clear(), iDfs[i] = oDfs[i] = 0, root[i] = 0;  // 清空
        for (int i = 1; i < n; i++) edge[parents[i]].push_back(i);  // 建树
        dfn = 0; dfs(0, -1);
        
        // 下面是更新主席树
        tree[0].sum = tree[0].ch[0] = tree[0].ch[1] = 0;
        numn = root[0] = 0;
        for (int i = 1; i <= n; i++) insert(root[i], root[i - 1], 1, 1e5, nums[rDfs[i]]);
        
        vector<int> ans;
        for (int i = 0; i < n; i++){
            int left = 1, right = 1e5, rec = 0;
            while(left <= right){
                int mid = (left + right) / 2;
                int ret = query(root[oDfs[i]], root[iDfs[i] - 1], 1, 1e5, 1, mid);
                if (ret == mid){
                    rec = max(rec, mid);
                    left = mid + 1;
                }else right = mid - 1;
            }
            ans.push_back(rec + 1);
        }
        
        return ans;
    }
};

本题还有其他两个解法，很妙，这里摘抄一下巨佬的go语言题解[4]如下两个。

思路三：启发式合并

遍历整棵树，统计每棵子树包含的基因值集合，以及缺失的最小基因值（记作

\textit{mex}

）。合并基因值集合时，总是从小的往大的合并（类似并查集的按秩合并），同时更新当前子树的

\textit{mex}

的最大值。合并完成后再不断自增子树的

\textit{mex}

直至其不在基因值集合中。

这一方法同时也适用于有相同基因值的情况。

时间复杂度：

O(n\log n)

。证明[5]。

func smallestMissingValueSubtree(parents []int, nums []int) []int {
    n := len(parents)
    g := make([][]int, n)
    for w := 1; w < n; w++ {
        v := parents[w]
        g[v] = append(g[v], w)
    }
    mex := make([]int, n)
    var f func(int) map[int]bool
    f = func(v int) map[int]bool {
        inSet := map[int]bool{}
        mex[v] = 1
        for _, w := range g[v] {
            s := f(w)
            // 启发式合并：保证从小的集合合并到大的集合
            if len(s) > len(inSet) {
                inSet, s = s, inSet
            }
            for x := range s {
                inSet[x] = true
            }
            if mex[w] > mex[v] {
                mex[v] = mex[w]
            }
        }
        inSet[nums[v]] = true
        for inSet[mex[v]] {
            mex[v]++ // 不断自增直至 mex[v] 不在集合中
        }
        return inSet
    }
    f(0)
    return mex
}

思路四：利用无重复基因值的性质

由于没有重复基因，若存在一个节点 x，其基因值为 1，那么从 x 到根这一条链上的所有节点，由于子树包含 x，其

\textit{mex}

均大于 1，而其余不在链上的节点，由于子树不包含 x，故其

\textit{mex}

均为 1。因此，我们只需要计算在这条链上的节点的

\textit{mex}

值。

我们可以从 x 出发，顺着父节点往根走，同时收集当前子树下的所有基因值，然后再不断自增子树的

\textit{mex}

直至其不在基因值集合中。

时间复杂度：

O(n)

。

func smallestMissingValueSubtree(parents []int, nums []int) []int {
    n := len(parents)
    mex := make([]int, n)
    for i := range mex {
        mex[i] = 1
    }

    g := make([][]int, n)
    for w := 1; w < n; w++ {
        v := parents[w]
        g[v] = append(g[v], w)
    }

    inSet := map[int]bool{}
    var f func(int)
    f = func(v int) {
        inSet[nums[v]] = true // 收集基因值
        for _, w := range g[v] {
            if !inSet[nums[w]] { // 避免重复访问节点
                f(w)
            }
        }
    }

    // 找到基因值等于 1 的节点 x
    x := -1
    for i, v := range nums {
        if v == 1 {
            x = i
            break
        }
    }
    // x 顺着父节点往上走
    for cur := 2; x >= 0; x = parents[x] {
        f(x)
        for inSet[cur] {
            cur++ // 不断自增直至不在基因值集合中
        }
        mex[x] = cur
    }
    return mex
}