Description
Given a binary tree by parent array, for each node compute product of sizes of its children subtrees and remaining tree. Count nodes with max score.
Examples
Input:
parents = [-1,2,0,2,0]Output:
3Explanation:
3 nodes with highest score.
Input:
parents = [1]Output:
1Explanation:
Edge case with a single-element array.
Input:
parents = [-1,0,0,1,1,2,2]Output:
4Explanation:
Tree has root 0 with children 1,2. Node 1 has children 3,4. Node 2 has children 5,6. When removing leaf nodes (3,4,5,6), each creates subtrees of sizes: remaining tree=6, no other subtrees=0. Score=6*1=6 for each leaf. When removing internal nodes, scores are lower. Four leaf nodes share the highest score of 6.
Constraints
- •
2 ≤ parents.length ≤ 10⁵