leetcode

0 class Solution {

1 public:

2 int countHighestScoreNodes(const vector<int> &parents) const {

3 const int n = size(parents);

4

5 vector<int> count(n, 0);

6 for (int i = 1; i < n; i++) {

7 count[parents[i]]++;

8 }

9

10 queue<int> q;

11 for (int i = 1; i < n; i++) {

12 if (!count[i]) q.push(i);

13 }

14

15 vector<int> below(n, 1);

16 while (q.front()) {

17 const int root = q.front();

18 q.pop();

19 const int parent = parents[root];

20

21 if (!--count[parent]) q.push(parent);

22 below[parent] += below[root];

23 }

24

25 vector<int> above(n, 0);

26 for (int i = 1; i < n; i++) {

27 above[i] = below[0] - below[i];

28 }

29

30 vector<long long> score(n, 1);

31 for (int i = 1; i < n; i++) {

32 score[parents[i]] *= below[i];

33 score[i] *= above[i];

34 }

35

36 int res = 0;

37 long long maxi = 0;

38 for (const auto n : score) {

39 if (n == maxi) res++;

40 if (n > maxi) {

41 maxi = n;

42 res = 1;

43 }

44 }

45

46 return res;

47 }

48 };