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.

&nbsp;
Example 1:

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:

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.


&nbsp;
Constraints:


	n == parents.length
	2 &lt;= n &lt;= 105
	parents[0] == -1
	0 &lt;= parents[i] &lt;= n - 1 for i != 0
	parents represents a valid binary tree.


class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        graph = collections.defaultdict(list)
        for node, parent in enumerate(parents):  # build graph
            graph[parent].append(node)
        n = len(parents)                         # total number of nodes
        d = collections.Counter()
        def count_nodes(node):                   # number of children node + self
            p, s = 1, 0                          # p: product, s: sum
            for child in graph[node]:            # for each child (only 2 at maximum)
                res = count_nodes(child)         # get its nodes count
                p *= res                         # take the product
                s += res                         # take the sum
            p *= max(1, n - 1 - s)               # times up-branch (number of nodes other than left, right children ans itself)
            d[p] += 1                            # count the product
            return s + 1                         # return number of children node + 1 (self)
        count_nodes(0)                           # starting from root (0)
        return d[max(d.keys())]                  # return max count
class Solution {
    long max = 0, res = 0;
    public int countHighestScoreNodes(int[] parents) {
        Map<Integer, List<Integer>> hm = new HashMap();
        for(int i = 0; i < parents.length; i++) {   // build the tree
            hm.computeIfAbsent(parents[i], x ->new ArrayList<>()).add(i);
        }
        dfs(0, parents.length, hm); // traverse the tree to get the result
        return (int)res;
    }
    int dfs(int s, int n, Map<Integer, List<Integer>> hm) {
        int sum = 1;
        long mult = 1L;
        for(int child : hm.getOrDefault(s, new ArrayList<>())) {
            int count = dfs(child, n, hm); // subtree node count
            sum += count;
            mult *= count; // multiply the result by children size
        }     
        mult *= (s == 0 ? 1L : n - sum); // multiply the result by remain size except self and children size(the nodes through parent)
        if(mult > max) {
            max = mult;
            res = 1;
        } else if (mult == max) {
            res++;
        }
        return sum; // return the node count of the tree rooted at s
    }
}
class Solution {
public:
    
     
    // Steps : 
    // 1 - For each node, you need to find the sizes of the subtrees rooted in each of its children.
    
    // 2 - How to determine the number of nodes in the rest of the tree? 
	// Can you subtract the size of the subtree rooted at the node from the total number of nodes of the tree?
    
    // 3 - Use these values to compute the score of the node. Track the maximum score, and how many nodes achieve such score. 
    
	// calculating size of each subtree by standing at every node  '0' to 'n-1'
    int dfs(int src,vector<vector<int>>& g,vector<int>& size)
    {
         int ans = 1;// for curent node
         for(auto child : g[src]){
             ans += dfs(child,g,size);
         }
         return size[src] = ans; 
     }
    
    // This code can also be work for generalized tree not only for Binary tree
    int countHighestScoreNodes(vector<int>& parents) 
    {    
        int n=parents.size();
        vector<int>size(n,0);  // size[i] indicates size of subtree(rooted at i node) + 1
        vector<vector<int>>g(n);  // storing left and right child of a node
        for(int i=1;i<n;i++){
            g[parents[i]].push_back(i); // 'There is no parent for 0th node'
        }
        
        dfs(0,g,size); //calculating size of each subtree(rooted at ith node)

        long long int maxCount = 0; // To avoid overflow  because perform product below you should take "long long int"
        long long int maxScore = 0;
        for(int i=0;i<n;i++) // Nodes from '0' to 'n-1'
        {
            // calculate score of each node after removal their 'edge' or 'node itself'.
            long long int product = 1;
            product = max(product, (long long int)(n - size[i])); // calculating leftover nodes excluding child nodes 
            for(auto x : g[i])
            {
                product = product*size[x];
            }
            
            if(product > maxScore){
                maxScore = product;
                maxCount = 1;
            }
            else if(product == maxScore){
                maxCount++; // store count of nodes which have maximum score equal to "maxScore"
            }
        }
            
        return maxCount;
    }
};
var countHighestScoreNodes = function(parents) {
    const n = parents.length;
    const adj = [];
    
    for (let i = 0; i < n; ++i) {
        adj[i] = [];
    } 
    
    for (let i = 1; i < n; ++i) {
        const parent = parents[i];
        adj[parent].push(i);
    }
    
    let maxProd = 0;
    let maxCount = 0;
    
    dfs(0);
    
    return maxCount;
    
    function dfs(node) {
        let rem = n - 1;

        let sum = 0;
        let prod = 1;

        for (const child of adj[node]) {
            const count = dfs(child);
            
            sum += count;
            prod *= count;
            rem -= count;
        }

        if (rem > 0) prod *= rem;

        if (prod > maxProd) {
            maxProd = prod;
            maxCount = 1;
        }
        else if (prod === maxProd) {
            ++maxCount;
        }

        return sum + 1;
    }
};
Count Nodes With the Highest Score