Split Tree to Maximize Product

Given a binary tree root, consider deleting an edge in the tree so that the tree becomes disjoint with two trees. Then, take the sum of each subtree and multiply the two numbers. Return the largest such product we can get after deleting one edge.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Split-Tree-to-Maximize-Product

Examples

Example 1

Input

• root =

Output

• answer = 50

Explanation

If we delete the 3 - 5 edge, then we can have (1 + 2 + 3 + 4) * 5 = 50

Solution