J9 实践-2 装饰树

题目描述

信奥队为了营造即将到来的春节，所有同学会装饰树木。为了方便描述，我们用一个有根的数字树来表示一棵真正的树木。这个数字树有 $N$ 个元素，从 $1 \sim N$ 标号，$1$ 号元素为树根。每个非树根元素（编号大于1的元素）都有一个父元素 $P_e$，$1$ 号元素没有父亲（在输入数据中用 $-1$ 表示）。 每个元素 $i$ 都有一棵以此元素为根的相应的子树。我们在装饰树木的时候希望元素i对应的子树至少拥有 $C_i$个装饰物。同时，我们也希望放置这些装饰物所花费的总时间尽量少些（将 $k$ 个装饰物放置在元素 $i$ 的位置需要花费 $K\times T_i$ 个单位时间）。 请你帮忙计算一下，最少需要花费多少时间，才能完成一棵树的装饰工作。

输入格式

输入数据共若干行。第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含三个用空格隔开的整数 $P_i$，$C_i$ 和 $T_i$。

输出格式

输出数据仅一个整数，表示所需的最少时间。结果可能会超过 $32$ 位整数的范围，但不会超过 $64$ 位整数的范围。

样例输入1

5
-1 9 3
1 2 2
5 3 2
5 1 4
2 3 3

样例输出1

20

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le N \le 100,000$, $0 \le C_i \le 10,000,000$，$1 \le T_i \le100$。