Tap here to switch tabs
Problem
Submissions

Problem: Smallest Missing Genetic Value in Each Subtree

Try to solve the Smallest Missing Genetic Value in Each Subtree problem.

Statement

There is a tree rooted at node 00 consisting of n nodes labeled from 00 to n −1- 1. You are given an integer array parents of length n, where parents[i] is the parent of node i. Since node 00 is the root, parents[0] is equal to −1-1.

You are also given an integer array nums of length n, where nums[i] represents the genetic value of node i. All elements in nums are distinct.

Return an array ans of length n where ans[i] is the smallest missing positive integer (starting from 11) in the subtree rooted at node i.

The subtree of a node x consists of node x and all of its descendants.

Constraints:

  • n ==== parents.length ==== nums.length

  • 2≤2 \leq n ≤105\leq 10^5

  • 0≤0 \leq parents[i] ≤\leq n −1- 1 for i ≠0\neq 0

  • parents[0] ==−1== -1

  • parents represents a valid tree.

  • 1≤1 \leq nums[i] ≤105\leq 10^5

  • Each nums[i] is distinct.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Smallest Missing Genetic Value in Each Subtree

Try to solve the Smallest Missing Genetic Value in Each Subtree problem.

Statement

There is a tree rooted at node 00 consisting of n nodes labeled from 00 to n −1- 1. You are given an integer array parents of length n, where parents[i] is the parent of node i. Since node 00 is the root, parents[0] is equal to −1-1.

You are also given an integer array nums of length n, where nums[i] represents the genetic value of node i. All elements in nums are distinct.

Return an array ans of length n where ans[i] is the smallest missing positive integer (starting from 11) in the subtree rooted at node i.

The subtree of a node x consists of node x and all of its descendants.

Constraints:

  • n ==== parents.length ==== nums.length

  • 2≤2 \leq n ≤105\leq 10^5

  • 0≤0 \leq parents[i] ≤\leq n −1- 1 for i ≠0\neq 0

  • parents[0] ==−1== -1

  • parents represents a valid tree.

  • 1≤1 \leq nums[i] ≤105\leq 10^5

  • Each nums[i] is distinct.