Formatted question description: https://leetcode.ca/all/2003.html

# 2003. Smallest Missing Genetic Value in Each Subtree (Hard)

There is a **family tree** rooted at `0`

consisting of `n`

nodes numbered `0`

to `n - 1`

. You are given a **0-indexed** integer array `parents`

, where `parents[i]`

is the parent for node `i`

. Since node `0`

is the **root**, `parents[0] == -1`

.

There are `10`

genetic values, each represented by an integer in the ^{5}**inclusive** range `[1, 10`

. You are given a ^{5}]**0-indexed** integer array `nums`

, where `nums[i]`

is a **distinct **genetic value for node `i`

.

Return *an array *`ans`

* of length *`n`

* where *`ans[i]`

* is* *the smallest genetic value that is missing from the subtree rooted at node*

`i`

.The **subtree** rooted at a node `x`

contains node `x`

and all of its **descendant** nodes.

**Example 1:**

Input:parents = [-1,0,0,2], nums = [1,2,3,4]Output:[5,1,1,1]Explanation: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.

**Example 2:**

Input:parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]Output:[7,1,1,4,2,1]Explanation: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.

**Example 3:**

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

**Constraints:**

`n == parents.length == nums.length`

`2 <= n <= 10`

^{5}`0 <= parents[i] <= n - 1`

for`i != 0`

`parents[0] == -1`

`parents`

represents a valid tree.`1 <= nums[i] <= 10`

^{5}- Each
`nums[i]`

is distinct.

**Companies**:

Codenation

**Related Topics**:

Dynamic Programming, Tree, Depth-First Search, Union Find

## Solution 1. DFS

- Only the node with value 1 and its ancestors have missing value greater than 1. All other nodes must have missing value 1.
- We traverse from the node with value 1 through its ancestors until the root. For each node, we DFS to visit all its children to collect the values we’ve seen.
- Based on the values we’ve seen, we can use a single variable
`miss`

to keep track of the first missing value. This value is monotonically increasing.

```
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> smallestMissingValueSubtree(vector<int>& P, vector<int>& A) {
int N = P.size();
vector<int> ans(N, 1), seen(100002, 0);
auto it = find(begin(A), end(A), 1);
if (it == end(A)) return ans; // if there is no node with value 1, all nodes can use 1.
vector<int> children[N];
for (int i = 1; i < N; ++i) children[P[i]].push_back(i);
int i = it - begin(A), miss = 1;
function<void(int)> dfs = [&](int i) {
if (seen[A[i]]) return;
for (int j : children[i]) dfs(j);
seen[A[i]] = 1;
};
while (i > -1) { // from the node of value 1, traverse all its ancestors
dfs(i);
while (seen[miss]) miss++;
ans[i] = miss;
i = P[i];
}
return ans;
}
};
```