DFS solution Python
\nclass Solution:\n    """\n    Deleting a node can yield at most 3 branches\n    """\n    def countHighestScoreNodes(self, parents: List[int]) -> int:\n       
```\nclass Solution:\n    """\n    Deleting a node can yield at most 3 branches\n    """\n    def countHighestScoreNodes(self, parents: List[int]) -> int:\n        \n        # build a graph representation\n        graph = collections.defaultdict(set)\n        for node, parent in enumerate(parents):\n            graph[parent].add(node)\n        \n        # total number of nodes, to be used\n        # to count the subtree obtained by removing\n        # a node but not the subtrees of node.left or node.right\n        n = len(parents)\n        \n        \n        # use a dict to record product-frequency pairs\n        d = collections.Counter()\n        \n        # a helper function\n        def dfs(node):\n            """\n            return number of nodes of the subtree rooted at node\n            """\n            p, s = 1, 0\n            # at most two children\n            for child in graph[node]:\n                res = dfs(child)\n                p *= res\n                s += res\n            # a possible branch from top of the node\n            p *= max(1, n - 1 - s)\n            d[p] += 1\n            return s + 1\n        \n        dfs(0)\n        return d[max(d.keys())]\n        \n```\n\nThis solution is motivated by \nhttps://leetcode.com/problems/count-nodes-with-the-highest-score/discuss/1537603/Python-3-or-Graph-DFS-Post-order-Traversal-O(N)-or-Explanation\n
[]