Advertisement
YEZAELP

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. };
Advertisement
RAW Paste Data Copied
Advertisement