Alpha Trees

5

1 votes
Problem

Our planet, Alpha Planet has weird trees (called Alpha Trees) that has circles with numbers in them. Each circle has at most two branches. The root has only one circle. Our superhero, Alphaboy is curious about the sum of maximum numbers on the left and the right sides.

In the tree above, 12 is in the circle in the root. Left side is composed of the branches starting with the left branch 4 and the right side starts the right branch 7. The maximum number on the left side is 41 whereas it is 33 on the right side.

Constraints:

  • Number of numbers; 1 < N <= 100,000.
  • All numbers are positive integers in the interval (1 ; 1,000,000,000).

Input format:

Is only one line; the tree. The representation of the tree is as follows:

  • Each circle will be represented as (number (left side) (right side))
  • ‘()’ indicates that the circle doesn’t have a branch on that side. 
  • There is exactly one space before each ‘(’ character excluding the starting one.

Output format:

  • Consist of only one line; the sum of the maximum numbers on the left and the right sides.

(Problem credit: Fatih Gelgi)

Time Limit: 1
Memory Limit: 32
Source Limit:
Explanation

The tree figure above is represented as in the sample input. The circle that has 6 on the left side is represented as follows: (6 () ()). 

Similarly, the circle of 41 is: (41 (6 () ()) (20 () ()). 41 and 33 are maximum numbers on the left and the right sides, so that the output is 74.

Editor Image

?