# LeetCode: Count Nodes With the Highest Score

Dec 13th, 2021
575
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2. public:
3.
4.     vector <int> g[100010];
5.     int node[100010];
6.
7.     int dfs(int u, int p){
8.         node[u] = 1;
9.         for(auto v: g[u]){
10.             if(v != p){
11.                 node[u] += dfs(v, u);
12.             }
13.         }
14.         return node[u];
15.     }
16.
17.     int countHighestScoreNodes(vector<int>& parents){
18.         int n = parents.size();
19.         for(int u=1;u<=n-1;u++){
20.             int v = parents[u];
21.             g[parents[u]].push_back(u);
22.         }
23.
24.         dfs(0, -1);
25.
26.         long long mx = 0;
27.         int cnt = 0;
28.         for(int u=0;u<=n-1;u++){
29.             long long cost = max(1, n - node[u]);
30.             for(auto v: g[u])
31.                 cost = (long long)((long long) cost * (long long) node[v]);
32.             if(cost > mx) mx = cost, cnt = 1;
33.             else if(cost == mx) cnt ++;
34.         }
35.
36.         return cnt;
37.     }
38. };