Count nodes with the highest score

Array Tree Depth-First Search Binary Tree

52.5% acceptance

Feb 25, 2026

1183

100

There is a binary tree rooted at 0 consisting of n nodes. The nodes are labeled from 0 to n - 1. You are given a 0-indexed integer array parents representing the tree, where parents[i] is the parent of node i. Since node 0 is the root, parents[0] == -1. Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees. Return the number of nodes that have the highest score.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_highest_score_nodes(parents: Vec<i32>) -> i32 {
    let n = parents.len();
    let mut children = vec![vec![]; n];
    for i in 1..n {
      children[parents[i] as usize].push(i);
    }

    // Compute subtree sizes via DFS
    let mut sub_size = vec![1usize; n];
    // Iterative post-order DFS
    let mut order = vec![];
    let mut stack = vec![0usize];
    while let Some(u) = stack.pop() {
      order.push(u);
      for &v in &children[u] {
        stack.push(v);
      }
    }
    for &u in order.iter().rev() {
      for &v in &children[u] {
        sub_size[u] += sub_size[v];
      }
    }

    let mut max_score = 0u64;
    let mut count = 0i32;
    for i in 0..n {
      let left = if children[i].len() > 0 { sub_size[children[i][0]] } else { 0 };
      let right = if children[i].len() > 1 { sub_size[children[i][1]] } else { 0 };
      let remaining = n - sub_size[i];
      let _score = left.max(1) as u64 * right.max(1) as u64 * remaining.max(1) as u64;
      // Adjust: only multiply non-zero components
      let score = {
        let mut s = 1u64;
        if left > 0 { s *= left as u64; }
        if right > 0 { s *= right as u64; }
        if remaining > 0 { s *= remaining as u64; }
        s
      };
      if score > max_score {
        max_score = score;
        count = 1;
      } else if score == max_score {
        count += 1;
      }
    }
    count
  }
}