Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardbitmask-dp

Smallest Missing Genetic Value in Each Subtree

Problem (restated)

A tree given by parents, unique genetic values nums[i]. For every node return the mex (smallest missing positive) of values in its subtree.

Intuition

Values are unique, so any subtree that does not contain 1 has mex 1. Only the node holding 1 and its ancestors can have mex > 1. Walk that path toward the root; DFS each newly attached subtree into a seen[] bitset of genetic values, then bump mex.

Approaches

Bitset mex along root path

Unverified

Time O(n)Space O(n)

Idea. Default ans = 1. Find the node with value 1 (if none, done). seen[v] marks genetic values already in the union of visited subtrees — a bitset, not a TSP mask. Climb to the root: DFS unmarked children, then while seen[mex]: mex++.

Walkthrough. parents=[-1,0,0,2], nums=[1,2,3,4] → [5,1,1,1]. [-1,0,1,0,3,3], [5,4,6,2,1,3] → [7,1,1,4,2,1]. No 1 in nums → all ones.

Trade-offs. Not classic TSP; the bitset is over values (≤ 10^5), so a boolean array beats a hash set. Each node is DFS’d once.

Solution

export function smallestMissingValueSubtree(parents: number[], nums: number[]): number[] {
  const n = parents.length;
  const ans = new Array<number>(n).fill(1);
  let one = -1;
  for (let i = 0; i < n; i++) {
    if (nums[i] === 1) {
      one = i;
      break;
    }
  }
  if (one < 0) return ans;
  const g: number[][] = Array.from({ length: n }, () => []);
  for (let i = 0; i < n; i++) {
    const p = parents[i]!;
    if (p >= 0) g[p]!.push(i);
  }
  const MAXV = 100002;
  const seen = new Array<boolean>(MAXV).fill(false);
  const vis = new Array<boolean>(n).fill(false);
  const dfs = (u: number): void => {
    if (vis[u]) return;
    vis[u] = true;
    const v = nums[u]!;
    if (v < MAXV) seen[v] = true;
    for (const w of g[u]!) dfs(w);
  };
  let mex = 1;
  let cur = one;
  while (cur >= 0) {
    dfs(cur);
    while (mex < MAXV && seen[mex]) mex++;
    ans[cur] = mex;
    cur = parents[cur]!;
  }
  return ans;
}

export function smallestMissingValueSubtree(parents: number[], nums: number[]): number[] {
  const n = parents.length;
  const ans = new Array<number>(n).fill(1);
  let one = -1;
  for (let i = 0; i < n; i++) {
    if (nums[i] === 1) {
      one = i;
      break;
    }
  }
  if (one < 0) return ans;
  const g: number[][] = Array.from({ length: n }, () => []);
  for (let i = 0; i < n; i++) {
    const p = parents[i]!;
    if (p >= 0) g[p]!.push(i);
  }
  const MAXV = 100002;
  const seen = new Array<boolean>(MAXV).fill(false);
  const vis = new Array<boolean>(n).fill(false);
  const dfs = (u: number): void => {
    if (vis[u]) return;
    vis[u] = true;
    const v = nums[u]!;
    if (v < MAXV) seen[v] = true;
    for (const w of g[u]!) dfs(w);
  };
  let mex = 1;
  let cur = one;
  while (cur >= 0) {
    dfs(cur);
    while (mex < MAXV && seen[mex]) mex++;
    ans[cur] = mex;
    cur = parents[cur]!;
  }
  return ans;
}

Template connection

Bitset as membership of values, not of a 20-item subset. The DP-like bump of mex along one root path is why this id sits on the bitmask-dp path.

Reflection

The default answer is 1. If no node has value 1, every answer stays 1. Otherwise climb from the node whose value is 1 up to the root.
seen is a bitset of genetic values, not a path mask. DFS the unmarked children, then raise mex while seen[mex] is set.
A subtree that does not contain 1 cannot raise the mex. Values accumulate along the path. A sibling branch is scanned on its own.