[Python] O(n)
Key insight:\n\nOnly node with genetic value 1 and its ancestors have smallest missing value larger than 1.\n\n\nclass Solution:\n    def smallestMissingValueSu
### Key insight:\n\nOnly node with genetic value `1` and its ancestors have smallest missing value larger than 1.\n\n```\nclass Solution:\n    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n        n = len(parents)\n        g = [[] for _ in range(n)]\n        for i, p in enumerate(parents):\n            if p != -1: g[p].append(i)\n        \n        res = [1] * n\n        if 1 not in nums: return res  # 1 is missing for all nodes\n        \n        seen = [False] * (n+1)  # record seen genetic values\n        def scan(p, prev):  # dfs. put all values in this subtree into seen[]\n            if nums[p] <= n: seen[nums[p]] = True\n            for q in g[p]:\n                if q != prev: scan(q, -1)  # prevent duplicated visits\n        \n        prev, p = -1, nums.index(1)\n        cur = 0  # max genetic value seen so far\n        while p != -1:\n            scan(p, prev)\n            while cur + 1 <= n and seen[cur+1]: cur += 1\n            res[p] = cur + 1\n            prev, p = p, parents[p]\n            \n        return res\n```
[]