Minimizing Moves to Balance a Plasticine Tree

Little Z, a clever elementary school student, constructed a tree‐shaped craft using plastic tubes and pieces of plasticine. In his creation, every piece of plasticine has a downward plastic tube attached. Some pieces extend two plastic tubes upward (forming a branching node), while others have several heavy colorful balls attached. However, the structure quickly toppled because it was unbalanced.

Little Z consulted his classmate, Little C, who, after reading about balance principles in an encyclopedia, discovered the following rule: For every plasticine that connects two upward tubes, if the difference in the load capacities suspended by the two tubes exceeds the weight of one colorful ball, then the structure becomes unstable. Here the colorful balls are heavy, while the weights of the plasticine and tubes can be neglected.

Since moving a colorful ball requires extra work to dismantle and re‐fix it, Little C wishes to achieve balance by moving as few colorful balls as possible. Can you help her?

More formally, consider a tree defined recursively as follows:

• A leaf is represented by an integer, which is the initial number of colorful balls attached.
• An internal node is represented as ( L R ) where L and R are the two subtrees attached via upward tubes.

The balanced condition requires that for any internal node assigned a total of S balls, the two subtrees must receive \(\lfloor S/2 \rfloor\) and \(\lceil S/2 \rceil\) balls (the assignment may be swapped between left and right). You are allowed to move colorful balls arbitrarily among the leaves. A move consists of transferring one ball from one leaf to another. Your task is to redistribute the balls so that the balanced condition is satisfied at every internal node while minimizing the number of moves.

Note: The total number of balls remains fixed. The minimum number of moves is defined as half the sum of absolute adjustments (since moving one ball decreases one leaf and increases another by one).

Input format: A single line containing the tree description. The tree is given in the following format:

• If the node is a leaf, it is represented by an integer.
• If the node is an internal node, it is represented as ( L R ) where L and R are the representations of its left and right subtrees respectively. There is a space between tokens.

Output format: A single integer, the minimum number of moves required to balance the tree.

Mathematical formulation: Let S be the total number of balls assigned to an internal node. Then if the left subtree is assigned S_L and the right subtree S_R, the balanced condition is:

[ |S_L - S_R| \le 1. ]

Your goal is to choose new ball counts for each leaf (nonnegative integers) such that for every internal node with S total balls the following holds:

[ \begin{cases} S_L = \lfloor S/2 \rfloor \text{ and } S_R = \lceil S/2 \rceil,
\text{or}\ S_L = \lceil S/2 \rceil \text{ and } S_R = \lfloor S/2 \rfloor. \end{cases} ]

The cost for a leaf is the absolute difference between the new number and the original count. The total cost of adjustments is the sum of costs over all leaves, and the minimum number of moves is half of this sum.

inputFormat

A single line string representing the tree. The tree is defined recursively as follows:

• If the node is a leaf, it is an integer (its initial ball count).
• If the node is internal, it is formatted as ( L R ) where L and R are the left and right subtree representations. Tokens are separated by spaces.

It is guaranteed that there is at least one leaf. The total number of test cases is small and all numbers are nonnegative integers.

outputFormat

Output a single integer – the minimum number of moves required to redistribute the colorful balls so that every internal node satisfies the balance condition.

sample

3

0