Well Site Selection

Problem Background

Special for beginners, ^_^

Problem Description

Consider a binary tree (shown below; the number inside each circle is the population living at that node, the number next to the circle is the node's id). You must drill a well at some node so that the sum of distances travelled by all residents is minimised. Adjacent nodes are at distance $1$.

For the tree shown: if the well is built at node $1$, the distance sum is $4 + 12 + 2\times 20 + 2\times 40 = 136$; if it is built at node $3$, the distance sum is $4\times 2 + 13 + 20 + 40 = 81 \dots$

Input Format

The first line contains one integer $n$: the number of nodes in the tree ($n \le 100$).

Each of the following $n$ lines describes one node, with three integers separated by (one or more) spaces:

• the first number is the population at the node;
• the second number is the left link, $0$ means no left child;
• the third number is the right link, $0$ means no right child.

Output Format

Print a single integer: the minimum possible distance sum.

Sample Input

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

Sample Output

81

Constraints

$n \le 100$.

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• Try every node as the well location. For a fixed well, compute each node's distance to it and add (distance) × (population); take the minimum over all choices.
• Distance in a tree is found by a simple traversal (BFS/DFS) from the well node.