Detailed explanation - DFS
Intuition\n- Any node which is below the node 1 or in any adjacent path of node 1 will have missing as 1. So we don\'t have to process such nodes\n- For other n
# Intuition\n- Any node which is below the node `1` or in any adjacent path of node `1` will have missing as `1`. So we don\'t have to process such nodes\n- For other nodes, start by calculating missing for node `1`, then go upwards till root node\n\n# Approach\n- Refer comments inline\n\n# Complexity\n- Time complexity: O(n) - because every node will be processed only once\n- Space complexity: O(n)\n\n# Code\n```python []\nclass Solution:\n    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n        n = len(parents)\n        self.tree = [[] for _ in range(n)]\n        self.visited = set()\n\n        # build the tree (adj list)\n        for i in range(1, n):\n            p = parents[i]\n            self.tree[p].append(i)\n\n        # by default, assume "1" to be missing number for all\n        ans = [1] * n\n\n        # find out the node with value 1.\n        # We have to evaluate missing for any node upwards from this node\n        # for other nodes, missing value has to be 1\n        one_idx = -1\n        for i in range(n):\n            if nums[i] == 1:\n                one_idx = i\n                break\n\n        # if there is no node with value 1, then all will have 1 as missing value\n        if one_idx == -1: return ans\n\n        missing = 1\n        curr, prev = one_idx, -1;   # track prev so that we don\'t process a subtree if already processed\n        while curr != -1:\n            # visit this subtree\n            for child in self.tree[curr]:\n                if child == prev: continue\n                self.dfs(child, nums)\n\n            self.visited.add(nums[curr])\n            \n            # find missing value\n            while missing in self.visited: missing += 1\n            ans[curr] = missing\n\n            # travel upwards in tree\n            prev, curr = curr, parents[curr]\n\n        return ans\n\n    # visit entire subtree starting from \'node\' and mark corresponding genetic value as visited\n    def dfs(self, node, nums):\n        self.visited.add(nums[node])\n        for child in self.tree[node]:\n            self.dfs(child, nums)\n```\n```java []\nclass Solution {\n    List<Integer>[] tree;\n    HashSet<Integer> visited;\n\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        var n = parents.length;\n        tree = new ArrayList[n];\n        visited = new HashSet<>();\n\n        // build the tree (adjacency list)\n        for (var i = 1; i < n; i++) {\n            var p = parents[i];\n            if (tree[p] == null) tree[p] = new ArrayList<>();\n            tree[p].add(i);\n        }\n\n        // by default, assume "1" to be missing number for all\n        var ans = new int[n];\n        Arrays.fill(ans, 1);\n\n        // find out the node with value 1.\n        // We have to evaluate missing for any node upwards from this node\n        // for other nodes, missing value has to be 1\n        var oneIdx = -1;\n        for (var i = 0; i < n; i++) {\n            if (nums[i] == 1) {\n                oneIdx = i;\n                break;\n            }\n        }\n\n        // if there is no node with value 1, then all will have 1 as missing value\n        if (oneIdx == -1) return ans;\n\n        var missing = 1;\n        int curr = oneIdx, prev = -1;   // track prev so that we don\'t process a subtree if already processed\n        while (curr != -1) {\n            // visit this subtree\n            var children = tree[curr];\n            if (children != null) {\n                for (var child : children) {\n                    if (child == prev) continue;\n                    dfs(child, nums);\n                }\n            }\n\n            visited.add(nums[curr]);\n\n            // find missing value\n            while (visited.contains(missing)) missing++;\n            ans[curr] = missing;\n\n            // travel upwards in tree\n            prev = curr;\n            curr = parents[curr];\n        }\n\n        return ans;\n    }\n\n    // visit entire subtree starting from \'node\' and mark corresponding genetic value as visited\n    private void dfs(int node, int[] nums) {\n        visited.add(nums[node]);\n        if (tree[node] == null) return; // no children\n        for (var child : tree[node])\n            dfs(child, nums);\n    }\n}\n```\n```csharp []\npublic class Solution {\n    List<int>[] tree;\n    HashSet<int> visited;\n\n    public int[] SmallestMissingValueSubtree(int[] parents, int[] nums) {\n        var n = parents.Length;\n        tree = new List<int>[n];\n        visited = new HashSet<int>();\n\n        // build the tree (adj list)\n        for(var i=1; i<n; i++){\n            var p = parents[i];\n            if(tree[p] == null) tree[p] = new List<int>();\n            tree[p].Add(i);\n        }\n\n        // by default, assume "1" to be missing number for all\n        var ans = Enumerable.Repeat(1, n).ToArray();\n\n        // find out the node with value 1.\n        // We have to evaluate missing for any node upwards from this node\n        // for other nodes, missing value has to be 1\n        var oneIdx = -1;\n        for(var i=0; i<n; i++){\n            if(nums[i] == 1){\n                oneIdx = i;\n                break;\n            }\n        }\n\n        // if there is no node with value 1, then all will have 1 as missing value\n        if(oneIdx == -1) return ans;\n\n        var missing = 1;\n        int curr = oneIdx, prev = -1;   // track prev so that we don\'t process a subtree if already processed\n        while(curr != -1){\n            // visit this subtree\n            var children = tree[curr];\n            if(children != null){\n                foreach(var child in children){\n                    if(child == prev) continue;\n                    DFS(child, nums);\n                }\n            }\n\n            visited.Add(nums[curr]);\n            \n            // find missing value\n            while(visited.Contains(missing)) missing++;\n            ans[curr] = missing;\n\n            // travel upwards in tree\n            (prev, curr) = (curr, parents[curr]);\n        }\n\n        return ans;\n    }\n\n    // visit entire subtree starting from \'node\' and mark corresponding genetic value as visited\n    private void DFS(int node, int[] nums){\n        visited.Add(nums[node]);\n        if(tree[node] == null) return; // no children\n        foreach(var child in tree[node])\n            DFS(child, nums);\n    }\n}\n```\n
['Depth-First Search', 'Java', 'Python3', 'C#']