dfs, segment tree
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:

    def __init__(self):
        from collections import defaultdict
        self.edges = defaultdict(list)
        self.tree = []
        self.ans = []
        self.n = 100000

    def construct(self):
        for i in range(self.n):
            self.tree[self.n + i] = 1 + i
        for i in range(self.n - 1, -1, -1):
            self.tree[i] = min(self.tree[i << 1], self.tree[i << 1|1])

    def update(self, i, val):
        j = self.n + i
        self.tree[j] = val
        while j > 1:
            self.tree[j >> 1] = min(self.tree[j], self.tree[j ^ 1])
            j >>= 1

    def query(self, i, j):
        k, m = self.n + i, self.n + j
        ans = 100001
        while k < m:
            if (k & 1):
                ans = min(ans, self.tree[k])
                k += 1
            if (m & 1):
                m -= 1
                ans = min(ans, self.tree[m])
            k >>= 1
            m >>= 1
        return ans

    def dfs(self, node, restricted, nums):
        self.update(nums[node] - 1, 100001)
        for x in self.edges[node]:
            if x != restricted:
                self.update(nums[x] - 1, 100001)
                self.ans[x] = 1
                self.dfs(x, restricted, nums)
    
    def smallestMissingValueSubtree(self, parents: list[int], nums: list[int]) -> list[int]:
        n = len(parents)
        start = n
        for i in range(n):
            self.edges[parents[i]].append(i)
            if nums[i] == 1:
                start = i
        if start == n:
            return [1] * n
        self.tree = [100001] * 2 * self.n
        self.ans = [0] * n
        self.construct()
        restricted = -1
        while start != -1:
            self.dfs(start, restricted, nums)
            num = self.query(0, self.n)
            self.ans[start] = num
            restricted = start
            start = parents[start]
        return self.ans
        
```
['Python3']