549. Top Scoring Nodes
A chess club runs an elimination ladder shaped like a tree of n players numbered 0 to n - 1. Player 0 is the champion at the top, and parents[i] is the player directly above player i in the ladder (parents[0] = -1). Each player has at most two players directly below them.
Imagine removing one player together with the ladder links attached to them; the ladder splits into one or more separate groups. The removal score of that player is the product of the sizes of all the resulting groups. Return how many players have the highest removal score among all n players.
Example 1
- Input:
- parents = [-1,0,0,1,1,2,2,3]
- Output:
- 1
- Explanation:
Removing the root leaves parts of 4 and 3 nodes, a score of 12; every other node scores at most 8, so only one node is on top.
Example 2
- Input:
- parents = [-1,0,1,2]
- Output:
- 2
- Explanation:
Removing the root or the last node leaves one part of size 3, and removing a middle node leaves parts of sizes 1 and 2, giving 2; the maximum score 3 is reached twice.
Constraints
1 ≤ n ≤ 105
parents[0] = -1, and for i > 0, 0 ≤ parents[i] < n; the array describes a tree rooted at 0
Every node has at most two children (so every score fits in a 64-bit integer)
A parent index may be larger than the child's index.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)