[Java] Topology order to calculate sub tree size
IntuitionUse topology order to calculate sub tree size for each nodeComplexity

Time complexity: O(N)


Space complexity: O(N)

Code
# Intuition
Use topology order to calculate sub tree size for each node

# Complexity
- Time complexity: O(N)

- Space complexity: O(N)

# Code
```java []
class Solution {
    public int countHighestScoreNodes(int[] parents) {
        // topology order to calculate sub tree size
        int n = parents.length;
        int[] inDegree = new int[n];
        for (int p : parents) {
            if (p != -1) inDegree[p]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) q.offer(i);
        }

        int[] subTreeSize = new int[n];
        Arrays.fill(subTreeSize, 1);
        while (!q.isEmpty()) {
            int top = q.poll();
            if (top == 0) continue;
            int parent = parents[top];
            if (--inDegree[parent] == 0) {
                q.offer(parent);
            }

            subTreeSize[parent] += subTreeSize[top];
        }

        long[] score = new long[n];
        Arrays.fill(score, 1);
        for (int i = 1; i < n; i++) {
            score[i] *= (subTreeSize[0] - subTreeSize[i]);
            int p = parents[i];
            score[p] *= subTreeSize[i];
        }

        long maxScore = -1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (score[i] > maxScore) {
                count = 1;
                maxScore = score[i];
            } else if (score[i] == maxScore) {
                count++;
            }
        }

        return count;
    }
}
```
['Java']