Python3 Recursive DFS Solution with Explanation
Approach\n Describe your approach to solving the problem. \nBuild a tree using the parents array. Keep track of maxScore and frequency with a dictionary. Track 
# Approach\n<!-- Describe your approach to solving the problem. -->\nBuild a tree using the parents array. Keep track of maxScore and frequency with a dictionary. Track number of nodes in a subtree with `countNodes` DFS. \n\nThere are 3 subtrees that we will need to count and multiply:\n1 Parent subtree up to node removed\n2 Left subtree of node removed\n3 Right subtree of node removed\n\nTreat this almost like a prefix sum problem when calculating how many nodes for each subtree. Multiply the 3 totals.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def countHighestScoreNodes(self, parents: List[int]) -> int:\n\n        def countNodes(root):\n            total = 1 + sum(countNodes(child) for child in tree[root])\n            nodes[root] = total\n            return total\n\n        #Build binary tree\n        tree = {i: [] for i in range(len(parents))}\n        for i, parent in enumerate(parents):\n            if parent != -1: tree[parent].append(i)\n\n        #Keep track of scores\n        maxScore = float(\'-inf\')\n        scores = defaultdict(int)\n        nodes = [0] * len(parents)\n        \n        #Build nodes array to track how many nodes in a subtree given a root\n        #Use this calculate the number of nodes in the conn components when a node is removed\n        if parents:\n            countNodes(0)\n\n        for node in range(len(parents)):\n\n            #There are 3 subtrees that we will need to count and multiply\n            #[1] Parent subtree up to node removed\n            #[2] Left subtree of node removed\n            #[3] Right subtree of node removed\n            score = max(1, nodes[0] - nodes[node])\n            for child in tree[node]:\n                score *= max(1, nodes[child]) #[2], [3]\n\n            #Count how many times we see this score\n            scores[score] += 1\n            maxScore = max(maxScore, score)\n            \n        return scores[maxScore]\n```
['Python3']