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

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

方法1：dfs（利用基因值不同的性质，先找1，后做1）

题解

题解中找1和做1的前提是：只有在含有1的链上，才满足单调递增（不严格，non-decreasing）。
不含1的其他所有分支的节点的ans都是1。

如图所示，只有含1的链（红色）上面的答案是单调递增的

两边dfs搜索，复杂度为

另外：

    for (auto c : g[u])
      if (has1[c]) dfs2(c, nums);
    for (auto c : g[u])
      if (!has1[c]) dfs3(c, nums);

必须先遍历含有1（在链上的节点），否则，先遍历不含1的节点会干扰到含1链上的答案计算：

这棵树就是例子：计算节点3的时候，原本是[1,2,3]，res[3]为4。但是如果先访问了左边的节点1，数字4就会被标记已经访问，已访问变成了[1,2,3,4]，res[3]就会被记为5。

const int N = 1e5 + 10;
class Solution {
 public:
  vector<vector<int>> g;
  bool has1[N], vis[N];
  vector<int> res;
  int now;

  void dfs1(int u, vector<int>& nums) {
    if (nums[u] == 1) has1[u] = true;
    for (auto c : g[u]) {
      dfs1(c, nums);
      has1[u] |= has1[c];
    }
  }
  void dfs3(int u, vector<int>& nums) {
    for (auto c : g[u]) dfs3(c, nums);
    vis[nums[u]] = true;
  }
  void dfs2(int u, vector<int>& nums) {
    for (auto c : g[u])
      if (has1[c]) dfs2(c, nums);
    for (auto c : g[u])
      if (!has1[c]) dfs3(c, nums);
    vis[nums[u]] = true;
    while (vis[now]) now++;
    res[u] = now;
  }

  vector<int> smallestMissingValueSubtree(vector<int>& parents,
                                          vector<int>& nums) {
    memset(has1, 0, sizeof has1), memset(vis, 0, sizeof vis);
    int n = nums.size();
    now = 1;
    res.resize(n, 1), g.resize(n, vector<int>());
    for (int i = 1; i < n; i++) {
      g[parents[i]].push_back(i);
    }
    dfs1(0, nums);
    dfs2(0, nums);
    return res;
  }
};

方法2：启发式合并

类似于并查集的按秩合并
树上启发式合并
思想很简单，就是每次都把小集合并到大集合中去。
复杂度

class Solution {
 public:
  vector<vector<int>> g;
  vector<int> mex;
  vector<int> arr;
  set<int> f(int v) {
    set<int> inSet;
    mex[v] = 1;
    for (int w : g[v]) {
      set<int> s = f(w);
      // 启发式合并：保证从小的集合合并到大的集合
      if (s.size() > inSet.size()) swap(s, inSet);

      for (auto x : s) inSet.insert(x);

      if (mex[w] > mex[v]) mex[v] = mex[w];
    }
    inSet.insert(arr[v]);
    while (inSet.count(mex[v])) {
      mex[v]++;  // 不断自增直至 mex[v] 不在集合中
    }
    return inSet;
  }
  vector<int> smallestMissingValueSubtree(vector<int>& parents,
                                          vector<int>& nums) {
    int n = parents.size();
    arr = nums;
    g.resize(n, vector<int>());
    mex.resize(n, 0);

    for (int i = 1; i < n; i++) {
      g[parents[i]].push_back(i);
    }

    f(0);
    return mex;
  }
};

两种做法有明显的时间差距：

n，利用性质dfs nlogn，启发式合并