2003. Smallest Missing Genetic Value in Each Subtree Hard

1/**
2 * [2003] Smallest Missing Genetic Value in Each Subtree
3 *
4 * 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.
5 * There are 10^5 genetic values, each represented by an integer in the inclusive range [1, 10^5]. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.
6 * 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.
7 * The subtree rooted at a node x contains node x and all of its descendant nodes.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/23/case-1.png" style="width: 204px; height: 167px;" />
11 * Input: parents = [-1,0,0,2], nums = [1,2,3,4]
12 * Output: [5,1,1,1]
13 * Explanation: The answer for each subtree is calculated as follows:
14 * - 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
15 * - 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
16 * - 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
17 * - 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/23/case-2.png" style="width: 247px; height: 168px;" />
21 * Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
22 * Output: [7,1,1,4,2,1]
23 * Explanation: The answer for each subtree is calculated as follows:
24 * - 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.
25 * - 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
26 * - 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
27 * - 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
28 * - 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
29 * - 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.
30 * 
31 * Example 3:
32 * 
33 * Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
34 * Output: [1,1,1,1,1,1,1]
35 * Explanation: The value 1 is missing from all the subtrees.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	n == parents.length == nums.length
41 * 	2 <= n <= 10^5
42 * 	0 <= parents[i] <= n - 1 for i != 0
43 * 	parents[0] == -1
44 * 	parents represents a valid tree.
45 * 	1 <= nums[i] <= 10^5
46 * 	Each nums[i] is distinct.
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/
52// discuss: https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn smallest_missing_value_subtree(parents: Vec<i32>, nums: Vec<i32>) -> Vec<i32> {
58        vec![]
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_2003() {
70    }
71}
72