# 2049. Count Nodes With the Highest Score

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public: int countHighestScoreNodes(vector& parents) { int ans = 0; vector> tree(parents.size()); for (int i = 0; i < parents.size(); ++i) { if (parents[i] == -1) continue; tree[parents[i]].push_back(i); } dfs(tree, 0, 0, ans); return ans; } private: int dfs(const vector>& tree, int u, long&& maxScore, int& ans) { int count = 1; long score = 1; for (const int v : tree[u]) { const int childCount = dfs(tree, v, move(maxScore), ans); count += childCount; score *= childCount; } const int aboveCount = tree.size() - count; score *= max(aboveCount, 1); if (score > maxScore) { maxScore = score; ans = 1; } else if (score == maxScore) { ++ans; } return count; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public int countHighestScoreNodes(int[] parents) { List[] tree = new List[parents.length]; for (int i = 0; i < tree.length; ++i) tree[i] = new ArrayList<>(); for (int i = 0; i < parents.length; ++i) { if (parents[i] == -1) continue; tree[parents[i]].add(i); } dfs(tree, 0); return ans; } private int ans = 0; private long maxScore = 0; private int dfs(List[] tree, int u) { int count = 1; long score = 1; for (final int v : tree[u]) { final int childCount = dfs(tree, v); count += childCount; score *= childCount; } final int aboveCount = tree.length - count; score *= Math.max(aboveCount, 1); if (score > maxScore) { maxScore = score; ans = 1; } else if (score == maxScore) { ++ans; } return count; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution: def countHighestScoreNodes(self, parents: List[int]) -> int: tree = [[] for _ in range(len(parents))] for i, parent in enumerate(parents): if parent == -1: continue tree[parent].append(i) ans = 0 maxScore = 0 def dfs(u: int) -> int: # Returns node count nonlocal ans nonlocal maxScore count = 1 score = 1 for v in tree[u]: childCount = dfs(v) count += childCount score *= childCount score *= len(parents) - count or 1 if score > maxScore: maxScore = score ans = 1 elif score == maxScore: ans += 1 return count dfs(0) return ans