n nodes numbered 0 to n - 1 is shaped like a binary tree rooted at node 0: every node has at most two children. You are given an array boss where boss[i] is the parent of node i, and boss[0] = -1.
The score of a node is computed like this: remove the node together with all its links. The network falls apart into one or more non-empty pieces, and the score is the product of their sizes (a piece's size is its number of nodes).
Return how many nodes share the highest score.boss=[-1, 0, 1, 1, 0] → 3
Removing node 0 leaves pieces of size 3 and 1: score 3. Removing node 1 leaves 1, 1 and 2: score 2. Removing any leaf 2, 3 or 4 leaves one piece of 4 nodes: score 4. Three nodes reach the maximum of 4.
boss=[-1, 0] → 2
Removing either node leaves a single node, so both score 1.
boss=[-1, 0, 1, 2, 3] → 3
A chain of 5 nodes. Removing an end node 0 or 4 leaves one piece of 4, and removing the middle node 2 leaves two pieces of 2. All three score 4, while nodes 1 and 3 only get 1 · 3 = 3.
n = len(boss) ≤ 10⁵boss[0] = -1, and for i ≠ 0: 0 ≤ boss[i] ≤ n - 1boss describes a valid binary treeboss=[-1, 0, 1, 1, 0]
3
Run checks the first 3 tests in your browser. Submit checks all 55 tests on the server, hidden ones included.