There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1. You are given a 0-indexed integer array parents, where parents[i] is the parent for node i. Since node 0 is the root, parents[0] == -1.

There are 105 genetic values, each represented by an integer in the inclusive range [1, 105]. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.

Return an array ans of length n where ans[i] is the smallest genetic value that is missing from the subtree rooted at node i.

The subtree rooted at a node x contains node x and all of its descendant nodes.

&nbsp;
Example 1:

Input: parents = [-1,0,0,2], nums = [1,2,3,4]
Output: [5,1,1,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.


Example 2:

Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
Output: [7,1,1,4,2,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value.
- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.


Example 3:

Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
Output: [1,1,1,1,1,1,1]
Explanation: The value 1 is missing from all the subtrees.


&nbsp;
Constraints:


	n == parents.length == nums.length
	2 &lt;= n &lt;= 105
	0 &lt;= parents[i] &lt;= n - 1 for i != 0
	parents[0] == -1
	parents represents a valid tree.
	1 &lt;= nums[i] &lt;= 105
	Each nums[i] is distinct.


class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        ans = [1] * len(parents)
        if 1 in nums:
            tree = {}
            for i, x in enumerate(parents):
                tree.setdefault(x, []).append(i)

            k = nums.index(1)
            val = 1
            seen = set()

            while k != -1:
                stack = [k]
                while stack:
                    x = stack.pop()
                    seen.add(nums[x])
                    for xx in tree.get(x, []):
                        if nums[xx] not in seen:
                            stack.append(xx)
                            seen.add(nums[xx])
                while val in seen: val += 1
                ans[k] = val
                k = parents[k]
        return ans
class Solution {
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = 1;
        }
        
        int oneIndex = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                oneIndex = i;
                break;
            }
        }
        
        // 1 not found
        if (oneIndex == -1) {
            return res;
        }
        
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 1; i < n; i++) {
            Set<Integer> children = graph.getOrDefault(parents[i], new HashSet<Integer>());
            children.add(i);
            graph.put(parents[i], children);
        }
        
        Set<Integer> visited = new HashSet<Integer>();
        
        int parentIter = oneIndex;
        int miss = 1;
        while (parentIter >= 0) {
            dfs(parentIter, graph, visited, nums);
            while (visited.contains(miss)) {
                miss++;
            }
            res[parentIter] = miss;
            parentIter = parents[parentIter];
        }
        return res;
    }
    
    public void dfs(int ind, Map<Integer, Set<Integer>> graph, Set<Integer> visited, int []nums) {
        if (!visited.contains(nums[ind])) {
            Set <Integer> children = graph.getOrDefault(ind, new HashSet<Integer>());
        
            for (int p : children) {
                dfs(p, graph, visited, nums);
            }
            visited.add(nums[ind]);
        }
    }
}
class Solution {
public:
    unordered_set<int> visited;
    vector<int> nums ;
    vector<vector<int>> adj;

    void dfs(int node){
        for(auto child:adj[node]){
            if(!visited.count(nums[child])){
                visited.insert(nums[child]);
                dfs(child);
            }
        }
    }

    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
        int n = parents.size(), missing = 1;
        adj.resize(n);
        vector<int> res;
        this->nums = nums;
        res.resize(n,1);

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

        int node = -1;
        for(int i=0; i<n; i++){
            if(nums[i] == 1) {
                node = i;
                break ;
            }
        }
        if(node == -1) return res;
        while(node != -1) {
            visited.insert(nums[node]);
            dfs(node);
            while(visited.count(missing)) missing++;
            res[node] = missing;
            node = parents[node];
        }
        return res;
    }
};
var smallestMissingValueSubtree = function(parents, nums) {
    let n=parents.length,next=[...Array(n)].map(d=>[]),used={}
    for(let i=1;i<n;i++)
        next[parents[i]].push(i)
    let dfs=(node)=>{
        if(used[nums[node]])
            return
        used[nums[node]]=true
        for(let child of next[node])
            dfs(child)
    }
    let cur=nums.indexOf(1),leftAt=1,res=[...Array(n)].map(d=>1)
    while(cur!==-1){
        dfs(cur)
        while(used[leftAt])
            leftAt++
        res[cur]=leftAt
        cur=parents[cur]
    }
    return res
};
Smallest Missing Genetic Value in Each Subtree