Problem

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 thenumber of nodes that have the highest score.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: parents = [-1,2,0,2,0]
Output: 3
Explanation:
- The score of node 0 is: 3 * 1 = 3
- The score of node 1 is: 4 = 4
- The score of node 2 is: 1 * 1 * 2 = 2
- The score of node 3 is: 4 = 4
- The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.

Example 2

1
2
3
4
5
6
7

Input: parents = [-1,2,0]
Output: 2
Explanation:
- The score of node 0 is: 2 = 2
- The score of node 1 is: 2 = 2
- The score of node 2 is: 1 * 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.

Constraints

  • n == parents.length
  • 2 <= n <= 10^5
  • parents[0] == -1
  • 0 <= parents[i] <= n - 1 for i != 0
  • parents represents a valid binary tree.

Solution

Method 1 – DFS for Subtree Sizes and Score Calculation

Intuition

To compute the score for each node, we need to know the size of each subtree. We can use DFS to calculate the size of each subtree, and then for each node, calculate the product of the sizes of the resulting subtrees if that node is removed.

Approach

  1. Build the tree from the parents array.
  2. Use DFS to compute the size of each subtree.
  3. For each node, calculate the score:
    • The score is the product of the sizes of the left subtree, right subtree, and the rest of the tree (if nonzero).
  4. Track the maximum score and count how many nodes achieve it.
  5. Return the count of nodes with the highest score.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int countHighestScoreNodes(vector<int>& parents) {
        int n = parents.size();
        vector<vector<int>> g(n);
        for (int i = 1; i < n; ++i) g[parents[i]].push_back(i);
        vector<int> sz(n, 1);
        function<void(int)> dfs = [&](int u) {
            for (int v : g[u]) {
                dfs(v);
                sz[u] += sz[v];
            }
        };
        dfs(0);
        long long mx = 0; int cnt = 0;
        for (int i = 0; i < n; ++i) {
            long long score = 1;
            for (int v : g[i]) score *= sz[v];
            if (i) score *= (n - sz[i]);
            if (score > mx) mx = score, cnt = 1;
            else if (score == mx) cnt++;
        }
        return cnt;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func CountHighestScoreNodes(parents []int) int {
    n := len(parents)
    g := make([][]int, n)
    for i := 1; i < n; i++ {
        g[parents[i]] = append(g[parents[i]], i)
    }
    sz := make([]int, n)
    var dfs func(int) int
    dfs = func(u int) int {
        sz[u] = 1
        for _, v := range g[u] {
            sz[u] += dfs(v)
        }
        return sz[u]
    }
    dfs(0)
    mx, cnt := 0, 0
    for i := 0; i < n; i++ {
        score := 1
        for _, v := range g[i] {
            score *= sz[v]
        }
        if i != 0 {
            score *= n - sz[i]
        }
        if score > mx {
            mx, cnt = score, 1
        } else if score == mx {
            cnt++
        }
    }
    return cnt
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int countHighestScoreNodes(int[] parents) {
        int n = parents.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int i = 1; i < n; i++) g[parents[i]].add(i);
        int[] sz = new int[n];
        dfs(0, g, sz);
        long mx = 0; int cnt = 0;
        for (int i = 0; i < n; i++) {
            long score = 1;
            for (int v : g[i]) score *= sz[v];
            if (i != 0) score *= (n - sz[i]);
            if (score > mx) { mx = score; cnt = 1; }
            else if (score == mx) cnt++;
        }
        return cnt;
    }
    private int dfs(int u, List<Integer>[] g, int[] sz) {
        sz[u] = 1;
        for (int v : g[u]) sz[u] += dfs(v, g, sz);
        return sz[u];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun countHighestScoreNodes(parents: IntArray): Int {
        val n = parents.size
        val g = Array(n) { mutableListOf<Int>() }
        for (i in 1 until n) g[parents[i]].add(i)
        val sz = IntArray(n)
        fun dfs(u: Int): Int {
            sz[u] = 1
            for (v in g[u]) sz[u] += dfs(v)
            return sz[u]
        }
        dfs(0)
        var mx = 0L; var cnt = 0
        for (i in 0 until n) {
            var score = 1L
            for (v in g[i]) score *= sz[v].toLong()
            if (i != 0) score *= (n - sz[i]).toLong()
            when {
                score > mx -> { mx = score; cnt = 1 }
                score == mx -> cnt++
            }
        }
        return cnt
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def countHighestScoreNodes(self, parents: list[int]) -> int:
        n = len(parents)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parents[i]].append(i)
        sz = [1] * n
        def dfs(u):
            for v in g[u]:
                dfs(v)
                sz[u] += sz[v]
        dfs(0)
        mx, cnt = 0, 0
        for i in range(n):
            score = 1
            for v in g[i]:
                score *= sz[v]
            if i:
                score *= n - sz[i]
            if score > mx:
                mx, cnt = score, 1
            elif score == mx:
                cnt += 1
        return cnt
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    pub fn count_highest_score_nodes(parents: Vec<i32>) -> i32 {
        let n = parents.len();
        let mut g = vec![vec![]; n];
        for i in 1..n {
            g[parents[i] as usize].push(i);
        }
        let mut sz = vec![1; n];
        fn dfs(u: usize, g: &Vec<Vec<usize>>, sz: &mut Vec<i32>) {
            for &v in &g[u] {
                dfs(v, g, sz);
                sz[u] += sz[v];
            }
        }
        dfs(0, &g, &mut sz);
        let mut mx = 0i64; let mut cnt = 0;
        for i in 0..n {
            let mut score = 1i64;
            for &v in &g[i] {
                score *= sz[v] as i64;
            }
            if i != 0 {
                score *= (n as i32 - sz[i]) as i64;
            }
            if score > mx {
                mx = score; cnt = 1;
            } else if score == mx {
                cnt += 1;
            }
        }
        cnt
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    countHighestScoreNodes(parents: number[]): number {
        const n = parents.length;
        const g: number[][] = Array.from({length: n}, () => []);
        for (let i = 1; i < n; i++) g[parents[i]].push(i);
        const sz = Array(n).fill(1);
        function dfs(u: number): void {
            for (const v of g[u]) {
                dfs(v);
                sz[u] += sz[v];
            }
        }
        dfs(0);
        let mx = 0, cnt = 0;
        for (let i = 0; i < n; i++) {
            let score = 1;
            for (const v of g[i]) score *= sz[v];
            if (i !== 0) score *= n - sz[i];
            if (score > mx) { mx = score; cnt = 1; }
            else if (score === mx) cnt++;
        }
        return cnt;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes, since we visit each node once for DFS and once for score calculation.
  • 🧺 Space complexity: O(n), for storing the tree and subtree sizes.