Description
Disclaimer : This problem has nothing to do with MST(Minimum Spanning Tree). You don't need solid algorithm basic to solve this problem.
After doing a bunch of dull tree problems, you become dizzy and the trees look like they are spinning in your view.
You see an expression tree. The tree in your view can spin in two directions:
-
Left Spin: For a tree rooted at node P, of which right child is node Q and the left child of Q is B, after a left spin, the new root becomes Q, the left child of Q becomes P, and the right child of P becomes B. If P doesn't have a right child (i.e. Q is null), left spin cannot be performed. -
Right Spin: For a tree rooted at node Q, of which left child is node P and the right child of P is B, after a right spin, the new root becomes P, the right child of P becomes Q, the left child of Q becomes B. If Q doesn't have a left child (i.e. P null), right spin cannot be performed.
After several (or zero) times of spinning, if the expression tree can still denote a valid expression, we say that the tree is a good spinning tree; otherwise we say that the tree is a bad spinning tree.
The evaluation of the tree changes after the tree spins. Given an evaluation tree, you want to know that what is the minimum evaluation among all good spinning trees.
Explanation of Sample IO
For the given expression tree, it has four good spinning trees which are shown in the below figure. Initially its evaluation is -8. After one left spin, its evaluation becomes 0. After two left spins, its evaluation becomes -6. After one right spin, its evaluation becomes 0. It is obvious that after three left spins or two right spins, the tree cannot donate a valid expression. Therefore the minimum spinning tree is the inital tree and therefore output -8.
Input
The first line of the input is an integer N(3 <= N <= 3x105), being the length of the prefix expression of the expression tree.
The next line is the expression tree (in prefix expression). The expression contains only +, -, * and digits. All the numbers in the expression are integers between 1 and 9.
Test Cases
-
For all test cases, it is guaranteed values during calculation is between [-109, 109], meaning that using 32-bit integer will not overflow (if your code does not have bugs).
-
1-st test case : same as sample IO
-
2-nd test case : N <= 50. It is guaranteed that there are only three good spinning trees : the giving tree, the tree that left spins once, and the tree that right spin once. (i.e. evaluate the three good spinning trees and output the minimum value, and then you get AC in this test case)
-
3-rd, 4-th test case : You can get AC using an O(N2) solution.
-
5-th test case : You need to come up with an O(N) solution to get an AC.
Output
Output the minimum evaluation among all good spinning trees.
Note that you should have a '\n' in the end.