My DAG Solution,
IntuitionUse DAG iterative not DFS with recursion.ApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Use DAG iterative not DFS with recursion.

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
import java.util.*;

class Solution {
    public int countHighestScoreNodes(int[] parents) {
        int n = parents.length;
        int[] childCount = new int[n]; // Tracks the number of children for each node
        int[][] subtreeSizes = new int[n][2]; // Stores sizes of left and right subtrees
        Map<Integer, List<Integer>> graph = new HashMap<>();

        // Build the DAG (parent-to-children relationship)
        for (int i = 0; i < n; i++) {
            graph.putIfAbsent(i, new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            graph.get(parents[i]).add(i);
            childCount[parents[i]]++;
        }

        // Find all leaf nodes
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (childCount[i] == 0) {
                queue.add(i);
            }
        }

        // Bottom-up traversal to calculate subtree sizes
        while (!queue.isEmpty()) {
            int current = queue.poll();
            int parent = parents[current];
            if (parent == -1) continue; // Skip the root node

            // Calculate subtree size for parent
            if (subtreeSizes[parent][0] == 0) {
                subtreeSizes[parent][0] = subtreeSizes[current][0] + subtreeSizes[current][1] + 1;
            } else {
                subtreeSizes[parent][1] = subtreeSizes[current][0] + subtreeSizes[current][1] + 1;
            }

            // Reduce the child count of the parent
            if (--childCount[parent] == 0) {
                queue.add(parent);
            }
        }

        // Calculate scores and determine the highest score
        long maxScore = 0;
        int countMaxScore = 0;

        for (int i = 0; i < n; i++) {
            long score = 1;
            int remainingNodes = n - 1 - subtreeSizes[i][0] - subtreeSizes[i][1];
            if (remainingNodes > 0) score *= remainingNodes;
            if (subtreeSizes[i][0] > 0) score *= subtreeSizes[i][0];
            if (subtreeSizes[i][1] > 0) score *= subtreeSizes[i][1];

            if (score > maxScore) {
                maxScore = score;
                countMaxScore = 1;
            } else if (score == maxScore) {
                countMaxScore++;
            }
        }

        return countMaxScore;
    }
}

```
['Java']