1
class Solution {
2
  public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
3
    int n = parents.length;
4
    int[] res = new int[n];
5
    for (int i = 0; i < n; i++) {
6
      res[i] = 1;
7
    }
8

9
    int oneIndex = -1;
10
    for (int i = 0; i < n; i++) {
11
      if (nums[i] == 1) {
12
        oneIndex = i;
13
        break;
14
      }
15
    }
16

17
    // 1 not found
18
    if (oneIndex == -1) {
19
      return res;
20
    }
21

22
    Map<Integer, Set<Integer>> graph = new HashMap<>();
23
    for (int i = 1; i < n; i++) {
24
      Set<Integer> children = graph.getOrDefault(parents[i], new HashSet<Integer>());
25
      children.add(i);
26
      graph.put(parents[i], children);
27
    }
28

29
    Set<Integer> visited = new HashSet<Integer>();
30

31
    int parentIter = oneIndex;
32
    int miss = 1;
33
    while (parentIter >= 0) {
34
      dfs(parentIter, graph, visited, nums);
35
      while (visited.contains(miss)) {
36
        miss++;
37
      }
38
      res[parentIter] = miss;
39
      parentIter = parents[parentIter];
40
    }
41
    return res;
42
  }
43

44
  public void dfs(int ind, Map<Integer, Set<Integer>> graph, Set<Integer> visited, int[] nums) {
45
    if (!visited.contains(nums[ind])) {
46
      Set<Integer> children = graph.getOrDefault(ind, new HashSet<Integer>());
47

48
      for (int p : children) {
49
        dfs(p, graph, visited, nums);
50
      }
51
      visited.add(nums[ind]);
52
    }
53
  }
54
}