DFS || O(N) Time and space
Intuition\nUse DFS, recursively move to the leaf nodes, calculate score, and return total child nodes from there.\n\n# Approach\nScore of a node = Non-zero Numb
# Intuition\nUse DFS, recursively move to the leaf nodes, calculate score, and return total child nodes from there.\n\n# Approach\nScore of a node = Non-zero Number of Left child nodes * Non-zero Number of right child nodes * Non-zero Number of remaiming nodes except child nodes and self node.\n\n# Complexity\n- Time complexity:\nO(N)\nEach node we are visiting only once.\nAnd returning the total child nodes from there.\n\n- Space complexity:\nO(N)\n\n# Code\n```python3 []\nfrom typing import List\n\n\nclass Solution:\n\n    def update_score_and_count(self, score):\n        print(score)\n        if self.max_score < score:\n            self.max_score = score\n            self.max_score_nodes = 1\n        elif self.max_score == score:\n            self.max_score_nodes += 1\n\n    def travserse(self, root: int):\n        if self.adj.get(root) == None:\n            score = self.total_nodes-1\n            self.update_score_and_count(score)\n            # left child of leaf = 0, right child of leaf = 0, total childs of caller node = 0+1(self)+0\n            return 1\n\n        total_child = 0\n        score = 1\n        for child in self.adj[root]:\n            # find the number of left and right childs.\n            count = self.travserse(child)\n            # if there is no left child then 0 will not be multiplied to score, similarly, for right and head node.\n            # only sub-trees with non-zero number of nodes will be multiplied.\n            if count != 0:\n                total_child += count\n                score *= count\n\n        # Suppose if there is node whose left, child, and parent(total nodes - left - child -1(self)), all 3 are present.\n        # So, the score due to left and right child is already calculated above,\n        # With the below operation we update the score with remaining nodes\n        if self.total_nodes-(1+total_child) != 0:\n            score *= (self.total_nodes-(1+total_child))\n        self.update_score_and_count(score)\n        total_nodes = total_child + 1  # total nodes = left childs + right childs + self node\n        return total_nodes\n\n    def create_adjacency_list(self, parents: List[int]):\n        self.adj: dict[int, List] = {}\n        for node in range(len(parents)):\n            if self.adj.get(parents[node]) == None:\n                self.adj[parents[node]] = []\n            self.adj[parents[node]].append(node)\n\n    def countHighestScoreNodes(self, parents: List[int]) -> int:\n        self.max_score = 0\n        self.max_score_nodes = 0\n        self.total_nodes = len(parents)\n\n        self.create_adjacency_list(parents)\n\n        self.travserse(0)\n        return self.max_score_nodes\n\n```
['Python3']