2049. Count Nodes With the Highest Score Medium

1/**
2 * [2049] Count Nodes With the Highest Score
3 *
4 * 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.
5 * 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.
6 * Return the number of nodes that have the highest score.
7 *  
8 * Example 1:
9 * <img alt="example-1" src="https://assets.leetcode.com/uploads/2021/10/03/example-1.png" style="width: 604px; height: 266px;" />
10 * Input: parents = [-1,2,0,2,0]
11 * Output: 3
12 * Explanation:
13 * - The score of node 0 is: 3 * 1 = 3
14 * - The score of node 1 is: 4 = 4
15 * - The score of node 2 is: 1 * 1 * 2 = 2
16 * - The score of node 3 is: 4 = 4
17 * - The score of node 4 is: 4 = 4
18 * The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.
19 * 
20 * Example 2:
21 * <img alt="example-2" src="https://assets.leetcode.com/uploads/2021/10/03/example-2.png" style="width: 95px; height: 143px;" />
22 * Input: parents = [-1,2,0]
23 * Output: 2
24 * Explanation:
25 * - The score of node 0 is: 2 = 2
26 * - The score of node 1 is: 2 = 2
27 * - The score of node 2 is: 1 * 1 = 1
28 * The highest score is 2, and two nodes (node 0 and node 1) have the highest score.
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	n == parents.length
34 * 	2 <= n <= 10^5
35 * 	parents[0] == -1
36 * 	0 <= parents[i] <= n - 1 for i != 0
37 * 	parents represents a valid binary tree.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/count-nodes-with-the-highest-score/
43// discuss: https://leetcode.com/problems/count-nodes-with-the-highest-score/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn count_highest_score_nodes(parents: Vec<i32>) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_2049() {
61    }
62}
63