Python 3: TC O(N log(N)), SC O(N): Slow, but Works for Duplicates
Intuition\n\nThis solution works if there are many copies of each number.\n\n## Faster Solution: Distinct Values\n\nIt turns out that the numbers are distinct. 
# Intuition\n\nThis solution works if there are many copies of each number.\n\n## Faster Solution: Distinct Values\n\nIt turns out that the numbers are distinct. That means that\n* `1` appears zero or one times\n* if `1` is not in `nums` then the min missing value in every subtree is `1`\n* otherwise we start with the node `u` with value `1`; we\'ll ascend the tree to root to set higher min missing values. All other subtrees will have min missing == 1\n* while `u` is not `-1`:\n  * run dfs on `u`, marking those nodes as seen, and also marking the values as seen\n  * then while `min_missing` is a value that has been seen in `u`\'s subtree, increment `min_missing`\n  * now `ans[u] = min_missing`\n  * and then we ascend to the parent of u, `u = parents[u]`\n\nThe idea is that only the node with value 1 and its ancestors can have a min missing value above 1.\n\nSo we first find the answer for the node with value `1`: explore its subtree to get a set of seen values or similar. Then while `min_missing in seen` we increment `min_missing`.\n\nThen we move to its parent:\n* min_missing is at least as high, because the parent has all of its child values\n* min_missing may have other children so we need to explore those trees as well, hence `dfs` for all nodes\n* and finally we repeat the `while min_missing in seen: min_missing += 1`\n\n## This Solution: Allows Duplicates\n\nMy idea was simpler:\n* the answer for a leaf is easy: if it\'s value is 1, the min missing is 2. Otherwise it\'s 1\n* for a parent:\n  * suppose the min missing of its children are `mm_1, mm_2, ..., mm_k` for `k` children\n  * the min_missing for the parent is at *least* `max(mm_1, .., mm_k)`\n  * if there are larger values in the child trees though then we should keep incrementing `mm` until it\'s really the first missing\n\nTo save a bit of space, for each set, I try to only add things to the set that are *above* the min missing value.\n\nTo avoid `O(n**2)` complexity by copying an `O(n)` sized tree `O(n)` times for a very unbalanced tree, I used the "union by rank" technique:\n* start with the largest child set\n* while there is another child set, add elements from the child set to the biggest set\n\nThen while `mm`, the current min missing is in the set, then remove `mm` from the set and increment `mm += 1`. Then we\'ll end with `mm` as the true min missing number, and `seen` will mostly only have elements larger than `mm`.\n\n# Complexity\n- Time complexity: `O(n log(n))`\n  - in the worst case the tree is perfectly balanced\n  - and therefore in the second to last level we\'ll merge sets with 1 value each\n  - then in the next level we\'ll merge sets with 3 values each\n  - then 7 values each\n  - the total work done in each level is `O(n)` because that\'s the total number of elements across all subtrees\n  - and there are `O(log(n))` levels\n  - the union-by-rank approach means a very unbalanced tree is the BEST case scenario because for each node in the long chain we\'ll add O(1) side elements to the large set and then continue\n\n- Space complexity: `O(n)`, a very deep tree will have `O(n)` stack frames. For top-level nodes the set of values above the min missing is also `O(n)`\n\n# Can the Faster Solution Handle Duplicates?\n\nIt can! But we would need a separate `seen` set or bit set for each node with value `1`. We\'d also need to ascend the `1`-to-root paths for each. In the worst case with `O(n)` copies of `1` we\'d spend `O(n**2)` time and `O(n*1e5)` space which is too much space, we\'ll get MLE for very large values.\n\nMaybe there\'s a way to optimize where we ascend deep nodes with value 1 to shallow, in the hopes that eventually those 1-to-root paths would converge on common ancestors and we could then just ascend from the common ancestors back to root.\n\n# Code\n```\nclass Solution:\n    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n        # n nodes numbered 0..n-1\n        # values 1..1e5\n\n        # something like for each node\n        #    > mark all subtree values\n        #    > find minimum missing, so if one is missing return 1, elif 2 is missing return 2, etc.\n\n        # suppose we have two child trees with min missing A and B\n        #  that means A has 1..A-1 and B has 1..B-1\n        #  then collectively the min missing is\n        #        at least B\n        #        if current value is B though then it\'s at least B+1\n        #         but if B+1 is present then we\'d have a complicated situation\n        #         where we\'d have to retraverse\n\n        # another idea: we can answer queries in any order\n\n        # 1 cannot be missing from any subtree with a 1\n        \n        # so maybe we approach from the direction of\n        #   > which subtrees are missing 1? leaves, up to the first with a 1\n        #   > which subtrees are missing 2? leaves up to the first with a 2\n\n\n        # as we descend the tree the earliest missing value decreases\n        # so let\'s try that idea again\n        #     when we descend from parent to child: remove parent node from counts, if counts is zero then\n        #     put parent.val at the end of a "missing stack" so as we descend we add new lower min missing, and when we ascend\n        #     we come back up\n\n        # problem: we need counts for each parent\n\n        # idea: maybe get counts for each child, leaves are easy: min missing is 1, unless curr val is 1 in which case it\'s 2\n        #\n        #   then at worst we\'d merge two O(n) lists, but that means we split about evenly\n\n        n = len(nums)\n        adj = [[] for _ in range(n)]\n        for v, p in enumerate(parents):\n            if p == -1: continue\n            adj[p].append(v)\n\n        min_missing = [0]*n\n\n        def set_min_missing(u: int) -> tuple[int, set[int]]:\n            """Returns the min missing value in u\'s subtree, and all values higher than mm in the subtree."""\n\n            if not adj[u]:\n                if nums[u] == 1:\n                    min_missing[u] = 2\n                    return 2, set() # no numbers above min missing\n                else:\n                    min_missing[u] = 1\n                    return 1, {nums[u]}\n\n            child_results = [set_min_missing(v) for v in adj[u]]\n            mm = max(r[0] for r in child_results) # each child has 1..r[0]-1 present so union will have r[0] or higher missing\n            child_results.sort(key=lambda s: len(s))\n\n            _, found_above = child_results.pop()\n            while child_results:\n                _, child_above = child_results.pop()\n                found_above.update(v for v in child_above if v >= mm)\n\n            if nums[u] >= mm:\n                found_above.add(nums[u])\n\n            while mm in found_above:\n                found_above.remove(mm)\n                mm += 1\n\n            min_missing[u] = mm\n            return mm, found_above\n\n        set_min_missing(0)\n\n        return min_missing\n```
['Python3']