医院设置

题目背景

在一棵给定的二叉树上，每个结点代表一个住户点并携带人口权重。相邻结点间的路程均为 \(1\)。现需选择一个结点建立医院，使得全体居民到该医院的加权路程之和最小。

题目描述

给定一棵含有 \(n\) 个结点的二叉树。每个结点 \(i\) 有：

• 人口 \(w_i\)；
• 左孩子编号 \(u_i\)（\(0\) 表示无左孩子）；
• 右孩子编号 \(v_i\)（\(0\) 表示无右孩子）。

树中所有边（父子关系）视为无向，任意相邻结点间距离为 \(1\)。请确定在哪个结点建立医院可以使加权距离和最小，并输出该最小值。

输入格式

• 第一行：一个整数 \(n\)（结点数）。
• 接下来 \(n\) 行：每行三个整数 \(w, u, v\)，分别表示该结点的人口与其左、右孩子编号（\(0\) 表示无该孩子）。

约定：结点按 \(1\ldots n\) 编号；输入保证结构为一棵树。

输出格式

• 输出一行，一个整数，表示最小加权距离和。

样例

输入

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

输出

81

样例解析

若医院建在结点 \(1\)，则总路程为 \(4 + 12 + 2\times20 + 2\times40 = 136\)； 若建在结点 \(3\)，则为 \(4\times2 + 13 + 20 + 40 = 81\)，更优。

数据范围

• \(1 \le n \le 100\)
• \(0 \le u, v \le n\)
• \(1 \le w \le 10^5\)