1
# Runtime: 3421 ms (Top 39.22%) | Memory: 51.8 MB (Top 96.08%)
2
class Solution:
3
    def smallestMissingValueSubtree(
4
        self, parents: List[int], nums: List[int]
5
    ) -> List[int]:
6
        ans = [1] * len(parents)
7
        if 1 in nums:
8
            tree = {}
9
            for i, x in enumerate(parents):
10
                tree.setdefault(x, []).append(i)
11

12
            k = nums.index(1)
13
            val = 1
14
            seen = set()
15

16
            while k != -1:
17
                stack = [k]
18
                while stack:
19
                    x = stack.pop()
20
                    seen.add(nums[x])
21
                    for xx in tree.get(x, []):
22
                        if nums[xx] not in seen:
23
                            stack.append(xx)
24
                            seen.add(nums[xx])
25
                while val in seen:
26
                    val += 1
27
                ans[k] = val
28
                k = parents[k]
29
        return ans