1
class Solution {
2
 public:
3
  unordered_set<int> visited;
4
  vector<int> nums;
5
  vector<vector<int>> adj;
6

7
  void dfs(int node) {
8
    for (auto child : adj[node]) {
9
      if (!visited.count(nums[child])) {
10
        visited.insert(nums[child]);
11
        dfs(child);
12
      }
13
    }
14
  }
15

16
  vector<int> smallestMissingValueSubtree(vector<int> &parents, vector<int> &nums) {
17
    int n = parents.size(), missing = 1;
18
    adj.resize(n);
19
    vector<int> res;
20
    this->nums = nums;
21
    res.resize(n, 1);
22

23
    for (int i = 1; i < n; i++) adj[parents[i]].push_back(i);
24

25
    int node = -1;
26
    for (int i = 0; i < n; i++) {
27
      if (nums[i] == 1) {
28
        node = i;
29
        break;
30
      }
31
    }
32
    if (node == -1) return res;
33
    while (node != -1) {
34
      visited.insert(nums[node]);
35
      dfs(node);
36
      while (visited.count(missing)) missing++;
37
      res[node] = missing;
38
      node = parents[node];
39
    }
40
    return res;
41
  }
42
};