python LCA O(n*h), Idea for Tarjan LCA O(n)
(at first i thought of prufer sequence)\nthe LCA part of this can be replaced by the following offline LCA algorithm which runs in O(n+q), where q is the number
(at first i thought of prufer sequence)\nthe LCA part of this can be replaced by the following offline LCA algorithm which runs in O(n+q), where q is the number of queries:\nhttps://www.wikiwand.com/en/Tarjan%27s_off-line_lowest_common_ancestors_algorithm?wprov=srpw1_1\n```\nfrom collections import defaultdict\n\nclass Solution:\n    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n        if 1 not in nums:\n            return [1 for _ in range(len(nums))]\n        # path from smallest gene to root, mark where gene x is required (LCAs of all genes up to x)\n        path,marks=set(),defaultdict(list)\n        orderedpath=[]\n        indices={n:i for i,n in enumerate(nums)}\n        # populate path with smallest gene\n        x=min(nums)\n        v=indices[x]\n        marks[v].append(x)\n        path.add(v)\n        orderedpath.append(v)\n        while 0 not in path:\n            v=parents[v]\n            path.add(v)\n            orderedpath.append(v)\n        # tree-based dp speeds up LCA\n        for x in sorted(nums)[1:]: # smallest gene taken care of\n            v=indices[x]\n            while v not in path:\n                v=parents[v]\n            marks[v].append(x)\n        # generate answer\n        ans=[1 for _ in range(len(nums))]\n        x, pool=0, set()\n        for v in orderedpath:\n            for y in marks[v]:\n                pool.add(y)\n            while x+1 in pool:\n                x+=1\n            ans[v]=x+1\n        return ans\n```
[]