Leetcode 2003. 每棵子树内缺失的最小值

(Updated: )
(5 mins to read)

题意

给定一棵n个节点，以0为根的无向树，每个节点有一个值num，问对于每个点u，u及其子树的所有值的mex。

$n \le 10^5, 1\le num \le 10 ^ 5$

做法

对于每个节点，我们维护一个桶数组和一个mex指针，然后从下往上转移即可（每次加一个点，就更新桶，然后尝试移动mex指针）。

但是我们不可能每个节点都开一个桶数组，时间和空间都受不了。

显然可以用dsu on tree来解决（常用与静态子树查询问题）。思路就是只用一个全局的桶数组和mex指针，先处理所有轻儿子的答案，然后清空贡献；再处理唯一的重儿子，但是保留贡献；最后再把所有轻儿子的贡献再统计一遍即可。

因为一个点往上最多分成log段重链，也就是这里每个轻儿子最多额外统计log次，因此只乘了个log的复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
        int n = parents.size();
        vector<vector<int>> G(n);
        for (int i = 1; i < n; i++) {
            G[parents[i]].push_back(i);
        }
        vector<int> sz(n), big_son(n, -1), ans(n);
        std::function<void(int, int)> get = [&](int u, int fa) {
            for (int v : G[u]) {
                if (v == fa) continue;
                get(v, u);
                sz[u] += sz[v];
                if (big_son[u] == -1 || sz[v] > sz[big_son[u]]) {
                    big_son[u] = v;
                }
            }
        };
        get(0, -1);
        vector<int> bucket(n + 1, 0), pending;
        int cur = 0;
        std::function<void(int, int)> add = [&](int u, int fa) {
            if (nums[u] - 1 < n) {
                bucket[nums[u] - 1]++;
                pending.push_back(nums[u]);
            }
            for (int v : G[u]) {
                if (v == fa) continue;
                add(v, u);
            }
        };
        std::function<void(int, int, bool)> dfs = [&](int u, int fa, bool del) {
            for (int v : G[u]) {
                if (v == fa) continue;
                if (v == big_son[u]) continue;
                dfs(v, u, true);
            }
            if (big_son[u] != -1) {
                dfs(big_son[u], u, false);
            }
            for (int v : G[u]) {
                if (v == fa) continue;
                if (v == big_son[u]) continue;
                add(v, u);
            }
            if (nums[u] - 1 < n) {
                bucket[nums[u] - 1]++;
                pending.push_back(nums[u]);
            }
            while (bucket[cur]) ++cur;
            ans[u] = cur + 1;
            if (del) {
                for (int num : pending) bucket[num - 1]--;
                pending.clear();
                cur = 0;
            }
        };
        dfs(0, -1, false);
        return ans;
    }
};

此外也可以每个点维护一个哈希集合（而不是桶数组），然后从下往上启发式合并（小的集合插入到大的集合）。

以上做法是通用的，但是这道题有一个特性是每个点的numm互不相同，也就意味着只有一个点的num为1，只有这个点往上的链的mex > 1，所以一遍dfs即可。