Description

Given a binary tree as shown:

The number inside each circle is the population at that node. The number beside each circle is the node index. Choose one node to build a hospital so that the total distance traveled by all residents is minimized. The distance between two adjacent nodes is $1$.

For example, if the hospital is built at node $1$, the total distance is $4 + 12 + 2 \times 20 + 2 \times 40 = 136$. If it is built at node $3$, the total distance is $4 \times 2 + 13 + 20 + 40 = 81$.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.

Each of the next $n$ lines describes one node with three integers $w, u, v$, where $w$ is the population at the node, $u$ is the left child (with $0$ meaning no child), and $v$ is the right child (with $0$ meaning no child).

Output Format

Output a single integer, the minimum total distance.

5						
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0

81

Hint

Constraints

For 100% of the testdata, it is guaranteed that $1 \leq n \leq 100$, $0 \leq u, v \leq n$, $1 \leq w \leq 10^5$.

Translated by ChatGPT 5