题目描述

给定一棵二叉树，每个结点有一定人口。相邻结点距离为1。选择一个结点建立医院，使所有居民到医院的路程总和最小。

输入格式

第一行n。接下来n行，每行人口数、左孩子编号、右孩子编号；0表示没有孩子。

输出格式

输出最小距离总和。

样例

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

81

数据范围

1≤n≤100；人口数为0至100000。