Java | 3 solutions: Node(1)-to-Root traversal vs. Union-Find vs. Brute Force with HashSet
Approach 1\nObserve that only the nodes in the direct path from root to node with value=1 ("node1") will have the minimum missing value>1 (the rest of the tree 
**Approach 1**\nObserve that only the nodes in the direct path from root to node with value=1 ("node1") will have the minimum missing value>1 (the rest of the tree will have this value == 1).\nAlgo:\n1. identify node with value=1 (if there is one)\n2. create a set of possible minimum missing values other than 1:  [2..n+1] (there\'s n nodes - the maximum such value will be n+1 in the worst case)\n3. work to find the missing values for nodes on path from node1 to root; for each node on this path:\n3.1. dfs into each unexplored child (with answer==0) and remove the node value from the sorted set, if it exists,\n3.2  take the remaining minimum value in the set as the answer\n\n```\nclass Solution {\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int n= parents.length, node1= -1;\n        int[] answer= new int[n];\n        TreeSet<Integer> values= new TreeSet<>();\n        for(int i=0; i<n; i++){\n            values.add(i+2);\n            if(nums[i]==1) node1= i;\n        }\n        if(node1==-1){ // no node has value 1, return all 1\'s\n            Arrays.fill(answer, 1);\n            return answer;\n        }\n        ArrayList<Integer>[] al= new ArrayList[n];\n        for(int i=0; i<n; i++) al[i]= new ArrayList<>();\n        for(int i=0; i<n; i++) if(parents[i]!=-1) al[parents[i]].add(i);\n\n        for(int node= node1; node!=-1; node= parents[node]){\n            dfs(node, al, nums, values, answer);\n            answer[node]= values.first();\n        }\n        return answer;\n    }\n    \n    void dfs(int i, ArrayList<Integer>[] al, int[] nums, TreeSet<Integer> values, int[] answer){\n       for(int j:al[i])\n            if(answer[j]==0) dfs(j, al, nums, values, answer);\n        values.remove(nums[i]); // remove if present\n        answer[i]= 1;\n    }\n}\n```\n\n**Approach 2**\nInterestingly, the problem can be solved without the observation limiting the traversal to a single-path - by using Union-Find.\nHere is a solution in Java- all credit to [Drunken](https://leetcode.com/Drunken/) and his Python solution presented [here](https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/discuss/1458284/Union-Find-with-thinking-process-%2B-A-Bonus-Variant!).\nThis time we\'re performing a regular DFS from root and efficiently merge the sets of encountered values using the Union-Find/Disjoint-Set data structure (rather than a collection of HashSets which would be quite slow - see Approach 3 giving TLE) - we then check such sets iteratively to find the minimum missing value.\n```\nclass Solution {\n    int n, ans[], uf[], nums[];\n    ArrayList<Integer>[] G;\n    \n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        this.n= parents.length;\n        this.nums= nums;\n        this.ans= new int[n];\n        this.G= new ArrayList[n];\n        int node1= -1, maxNum= 0;\n        for(int i=0; i<n; i++){\n            ans[i]= 1;\n            G[i]= new ArrayList<>();\n            if(nums[i]==1) node1= i;\n            maxNum= Math.max(maxNum, nums[i]);\n        }\n        if(node1==-1) return ans;\n        this.uf= new int[maxNum+2];\n        for(int i=0; i<n; i++){\n            if(parents[i]!=-1) G[parents[i]].add(i);\n            uf[i+1]= i+1;\n        }\n        dfs(0);\n        return ans;\n    }\n    \n    int find(int i){\n        while(uf[i]!=i) \n            i= uf[i]= uf[uf[i]];\n        return i;\n    }\n    \n    void dfs(int p){\n        int a= 1;\n        for(int ch:G[p]){\n            dfs(ch);\n            a= Math.max(a, ans[ch]);\n            uf[nums[ch]]= nums[p];\n        }\n        while(find(a)==nums[p]) ++a;\n        ans[p]= a;\n    }\n}\n```\n**Approach 3. Brute-Force with HashSet at each node (TLE)** same code as Approach 2 for comparison, but this time using a HashSet<Integer> per node, as opposed to Union Find - this is too slow and gives TLE\n```\nclass Solution {\n    int n, ans[], nums[];\n    ArrayList<Integer>[] G;\n    HashSet<Integer>[] sets;\n    \n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        this.n= parents.length;\n        this.nums= nums;\n        this.ans= new int[n];\n        this.G= new ArrayList[n];\n        int node1= -1;\n        for(int i=0; i<n; i++){\n            ans[i]= 1;\n            G[i]= new ArrayList<>();\n            if(nums[i]==1) node1= i;\n        }\n        if(node1==-1) return ans;\n        this.sets= new HashSet[n];\n        for(int i=0; i<n; i++){\n            if(parents[i]!=-1) G[parents[i]].add(i);\n            this.sets[i]= new HashSet<>();\n            this.sets[i].add(nums[i]);\n        }\n        dfs(0);\n        return ans;\n    }\n    \n    void dfs(int p){\n        int a= 1;\n        for(int ch:G[p]){\n            dfs(ch);\n            a= Math.max(a, ans[ch]);\n            sets[p].addAll(sets[ch]);\n        }\n        while(sets[p].contains(a)) ++a;\n        ans[p]= a;\n    }\n}\n```
[]