A power distribution network is a binary tree; each node has a positive integer load. Cutting one wire (removing exactly one parent-child edge) splits the network into two connected pieces. The split score is the product of the total load of the two pieces. Choose the wire to cut so that the split score is maximized, and report that maximum product.
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is a positive integer load or null for a missing child. Children of null nodes are omitted.
A single integer: the maximum split score.
Example 1
Input
3 2 3 4
Expected
20
Explanation
Total load is 9. Cutting above node 3 gives pieces 3 and 6 (product 18); cutting above node 4 gives pieces 4 and 5 (product 20). The best split score is 20.
Example 2
Input
7 1 2 3 4 5 6 7
Expected
192
Explanation
Total load is 28. Cutting above node 3 separates its subtree (3 + 6 + 7 = 16) from the rest (12), giving 16 * 12 = 192, the maximum.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →