[Python] DFS count nodes - 1,2,3 edges
User DFS to count all nodes for the tree.\nThen iterate through all nodes. There are 3 cases after removing a node:\n- it has 1 edge: n-1\n- it has 2 edges: chi
User DFS to count all nodes for the tree.\nThen iterate through all nodes. There are 3 cases after removing a node:\n- it has 1 edge: n-1\n- it has 2 edges: child_count * (n - 1 - child_count)\n- it has 3 edges: L_count * R_count * (n-1-L_count-R_count)\n\nNote: root 0 is a special case. Treat it seperately.\n\n```\nclass Solution:\n    def countHighestScoreNodes(self, parents: List[int]) -> int:\n        n = len(parents)\n        # build tree\n        children = collections.defaultdict(list)\n        for i in range(1, n):\n            children[parents[i]].append(i)\n        \n        # count nodes\n        d = {}\n        def dfs_count(node):\n            cnt = 1\n            for v in children[node]:\n                cnt += dfs_count(v)\n            d[node] = cnt\n            return cnt\n        \n        dfs_count(0)\n        \n        # root\n        max_cnt = 1\n        if len(children[0]) == 1:    # root has 1 child\n            max_val = n-1\n        else:    # root has 2 children\n            max_val = d[children[0][0]] * d[children[0][1]]\n        \n        # 1 to n-1\n        for i in range(1, n):\n            if len(children[i]) == 0:    # 1 link\n                val = n-1\n            elif len(children[i]) == 1:    # 2 links\n                val = d[children[i][0]] * (n - 1 - d[children[i][0]])\n            else:    # 3 links\n                val = d[children[i][0]] * d[children[i][1]] * (n - 1 - d[children[i][0]] - d[children[i][1]])\n            if val > max_val:\n                max_val = val\n                max_cnt = 1\n            elif val == max_val:\n                max_cnt += 1\n                \n        return max_cnt\n                \n                \n```
[]