Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Hardbitmask-dp

Smallest Missing Genetic Value in Each Subtree

Problem (yeniden ifade)

parents ile verilen ağaç, tekil genetik değerler nums[i]. Her düğüm için alt ağacındaki değerlerin mex’ini (en küçük eksik pozitif) döndür.

Sezgi

Değerler tekil, bu yüzden 1 içermeyen her alt ağacın mex’i 1. Yalnızca 1’i tutan düğüm ve ataları mex > 1 olabilir. O yolda köke yürü; her yeni bağlanan alt ağacı seen[] genetik değer bitset’ine DFS ile işaretle, sonra mex’i yükselt.

Yaklaşımlar

Kök yolunda bitset mex

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. Varsayılan ans = 1. Değeri 1 olan düğümü bul (yoksa bitti). seen[v] ziyaret edilen alt ağaçların birleşimindeki genetik değerleri işaretler — TSP maskesi değil, bitset. Köke tırman: işaretsiz çocukları DFS’le, sonra while seen[mex]: mex++.

Yürüyüş. 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]. nums’ta 1 yok → hepsi bir.

Trade-off. Klasik TSP değil; bitset değerler üzerinedir (≤ 10^5), bu yüzden boolean dizi hash set’ten iyi. Her düğüm bir kez DFS edilir.

Çözüm

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;
}

Şablon bağlantısı

Bitset, 20 öğelik alt küme değil değer üyeliği. Mex’in tek kök yolunda ilerlemesi bu id’nin bitmask-dp yolunda olmasının nedeni.

Yansıma

Varsayılan cevap 1. Değeri 1 olan düğüm yoksa herkes 1. Varsa o düğümden köke tırman.
seen genetik değerlerin bitset’i. İşaretsiz çocukları DFS’le, sonra seen[mex] durduğu sürece mex artar.
1’i içermeyen alt ağaç mex’i büyütemez. Değerler yol boyunca birikir, kardeş dal ayrı taranır.