<p>There is a <strong>family tree</strong> rooted at <code>0</code> consisting of <code>n</code> nodes numbered <code>0</code> to <code>n - 1</code>. You are given a <strong>0-indexed</strong> integer array <code>parents</code>, where <code>parents[i]</code> is the parent for node <code>i</code>. Since node <code>0</code> is the <strong>root</strong>, <code>parents[0] == -1</code>.</p>

<p>There are <code>10<sup>5</sup></code> genetic values, each represented by an integer in the <strong>inclusive</strong> range <code>[1, 10<sup>5</sup>]</code>. You are given a <strong>0-indexed</strong> integer array <code>nums</code>, where <code>nums[i]</code> is a <strong>distinct </strong>genetic value for node <code>i</code>.</p>

<p>Return <em>an array </em><code>ans</code><em> of length </em><code>n</code><em> where </em><code>ans[i]</code><em> is</em> <em>the <strong>smallest</strong> genetic value that is <strong>missing</strong> from the subtree rooted at node</em> <code>i</code>.</p>

<p>The <strong>subtree</strong> rooted at a node <code>x</code> contains node <code>x</code> and all of its <strong>descendant</strong> nodes.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/23/case-1.png" style="width: 204px; height: 167px;" />
<pre>
<strong>Input:</strong> parents = [-1,0,0,2], nums = [1,2,3,4]
<strong>Output:</strong> [5,1,1,1]
<strong>Explanation:</strong> The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/23/case-2.png" style="width: 247px; height: 168px;" />
<pre>
<strong>Input:</strong> parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
<strong>Output:</strong> [7,1,1,4,2,1]
<strong>Explanation:</strong> The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value.
- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
<strong>Output:</strong> [1,1,1,1,1,1,1]
<strong>Explanation:</strong> The value 1 is missing from all the subtrees.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == parents.length == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= parents[i] &lt;= n - 1</code> for <code>i != 0</code></li>
	<li><code>parents[0] == -1</code></li>
	<li><code>parents</code> represents a valid tree.</li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li>Each <code>nums[i]</code> is distinct.</li>
</ul>

class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        # n nodes numbered 0..n-1
        # values 1..1e5

        # something like for each node
        #    > mark all subtree values
        #    > find minimum missing, so if one is missing return 1, elif 2 is missing return 2, etc.

        # suppose we have two child trees with min missing A and B
        #  that means A has 1..A-1 and B has 1..B-1
        #  then collectively the min missing is
        #        at least B
        #        if current value is B though then it's at least B+1
        #         but if B+1 is present then we'd have a complicated situation
        #         where we'd have to retraverse

        # another idea: we can answer queries in any order

        # 1 cannot be missing from any subtree with a 1
        
        # so maybe we approach from the direction of
        #   > which subtrees are missing 1? leaves, up to the first with a 1
        #   > which subtrees are missing 2? leaves up to the first with a 2


        # as we descend the tree the earliest missing value decreases
        # so let's try that idea again
        #     when we descend from parent to child: remove parent node from counts, if counts is zero then
        #     put parent.val at the end of a "missing stack" so as we descend we add new lower min missing, and when we ascend
        #     we come back up

        # problem: we need counts for each parent

        # 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
        #
        #   then at worst we'd merge two O(n) lists, but that means we split about evenly

        n = len(nums)
        adj = [[] for _ in range(n)]
        for v, p in enumerate(parents):
            if p == -1: continue
            adj[p].append(v)

        min_missing = [0]*n

        def set_min_missing(u: int) -> tuple[int, set[int]]:
            """Returns the min missing value in u's subtree, and all values higher than mm in the subtree."""

            if not adj[u]:
                if nums[u] == 1:
                    min_missing[u] = 2
                    return 2, set() # no numbers above min missing
                else:
                    min_missing[u] = 1
                    return 1, {nums[u]}

            child_results = [set_min_missing(v) for v in adj[u]]
            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
            child_results.sort(key=lambda s: len(s))

            _, found_above = child_results.pop()
            while child_results:
                _, child_above = child_results.pop()
                found_above.update(v for v in child_above if v >= mm)

            if nums[u] >= mm:
                found_above.add(nums[u])

            while mm in found_above:
                found_above.remove(mm)
                mm += 1

            min_missing[u] = mm
            return mm, found_above

        set_min_missing(0)

        return min_missing
111400