# 2049. Count Nodes With the Highest Score
###### tags: `Leetcode` `Medium` `Tree`
Link: https://leetcode.com/problems/count-nodes-with-the-highest-score/
## 思路 $O(N)$ $O(N)$
The value of a node is the product of:

1. number of nodes in the left subtree,
2. number of nodes in the right subtree,
3. number of all other nodes, excluding the current one (n - left - right - 1)
4. We can just use DFS to count child nodes for (1) and (2), and we can then compute (3) as we know the total nubers of nodes.
## Code

class Solution {
    long maxScore;
    public int countHighestScoreNodes(int[] parents) {
        List<List<Integer>> tree = new ArrayList<>();
        for(int i=0; i<parents.length; i++){
            tree.add(new ArrayList<>());
        }
        for(int i=1; i<parents.length; i++){
            tree.get(parents[i]).add(i);
        }
        maxScore = 0;
        long[] scores = new long[parents.length];
        dfs(tree, scores, 0);
        
        int ans = 0;
        for(long score:scores){
            if(score==maxScore) ans++;
        }
        return ans;
    }
    private int dfs(List<List<Integer>> tree, long[] scores, int root){
        int c1=0, c2=0;
        if(tree.get(root).size()!=0) c1 = dfs(tree, scores, tree.get(root).get(0));
        if(tree.get(root).size()==2) c2 = dfs(tree, scores, tree.get(root).get(1));
        long currScore = Math.max(c1, 1)*Math.max(c2, 1);
        currScore = currScore*(long)(Math.max(tree.size()-c1-c2-1, 1));
        scores[root] = currScore;
        maxScore = Math.max(currScore, maxScore);
        return c1+c2+1;
    }
}