2049. Count Nodes With the Highest Score

Updated: 2024-03-12
1 min read
[]

On This Page

LeetCode problem 2049

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        def dfs(i: int, fa: int):
            cnt = score = 1
            for j in g[i]:
                if j != fa:
                    t = dfs(j, i)
                    score *= t
                    cnt += t
            if n - cnt:
                score *= n - cnt
            nonlocal res, mx
            if mx < score:
                mx = score
                res = 1
            elif mx == score:
                res += 1
            return cnt

        n = len(parents)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parents[i]].append(i)
        res = mx = 0
        dfs(0, -1)
        return res