Luobuyu's Blog

0%

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

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.6k 阅读时长 ≈ 1 分钟
从值为1的节点往上搜索。

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

题目描述：

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

总共有 105 个基因值，每个基因值都用 闭区间 [1, 105] 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是节点 i 的基因值，且基因值 互不相同 。

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

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

数据范围：

$2\le n \le 10^5$

$nums[i]$ 互不相同

题解：

首先找到 $nums[i] = 1$ 的节点，然后他的子树中的节点答案全是 $1$，因为 $nums[i]$ 互不相同，他们都缺少 $1$。

遍历该子树中的所有节点，记录 $nums[j]$ 的值，然后就可以找到 $nums[i]$ 缺失的 $mex$。 因为父亲节点的 $mex$ 肯定会大于等于孩子节点的 $mex$。所以从该节点往上爬，继续 dfs 父亲节点，（这里需要剪枝，孩子节点 $i$ 就不需要访问了）。然后继续找出来父亲节点的缺失值。

代码：

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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    vector<vector<int>> g;
    vector<int> smallestMissingValueSubtree(vector<int> &parents, vector<int> &nums)
    {
        int n = nums.size();
        vector<int> ans(n, 1);
        g.resize(n);
        for (int i = 0; i < n; ++i)
        {
            int u = parents[i];
            if (u == -1)
                continue;
            int v = i;
            g[u].emplace_back(v);
        }
        // 找 nums[i] = 1 的 i
        int index = find(nums.begin(), nums.end(), 1) - nums.begin();
        if (index == n)
            return ans;
        unordered_set<int> vis;
        // fa 其实表示他的孩子节点
        function<void(int u, int fa)> dfs = [&](int u, int fa)
        {
            vis.insert(nums[u]);
            for (int i = 0; i < g[u].size(); ++i)
            {
                int v = g[u][i];
                if (v == fa)
                    continue;
                dfs(v, u);
            }
        };
        int mex = 2;
        int cur = index, nex = -1;
        while (cur != -1)
        {
            dfs(cur, nex);
            while (vis.count(mex))
                ++mex;
            ans[cur] = mex;
            nex = cur;
            cur = parents[cur];
        }
        return ans;
    }
};