P3018 [USACO11MAR] Tree Decoration G
题目描述
给定一颗以 $1$ 为根的有根树，第 $i$ 个结点的父结点为 $P_i$（$P_1=-1$），在第 $i$ 个结点上挂一个装饰物的代价为 $T_i$，每个结点可以挂任意个。现在给定每棵树子树中至少挂的装饰物个数 $C_i$，求满足要求的最少花费。
$1 \leq n \leq 10^5$，$1 \leq T_i \leq 100$，$1 \leq C_i \leq 10^7$，请注意要开 long long。
输入格式
第一行一个整数 $n$。
第 $1$ 行至第 $n$ 行，在第 $i+1$ 行有三个整数，分别表示 $P_i$，$C_i$ 和 $T_i$。
输出格式
一行一个整数表示最小花费。
### 样例解释
```
样例中给出的树如下：
1
|
2
|
5
/ \
4 3
给定如下数据：
该子树中所需的装饰物个数
| 在该节点挂一个装饰物的花费
| |
结点编号 | C_i | T_i
--------+--------+-------
1 | 9 | 3
2 | 2 | 2
3 | 3 | 2
4 | 1 | 4
5 | 3 | 3
最佳方案如下：
1 [0/9(0)]
|
2 [3/9(6)]
|
5 [0/6(0)]
/ \
[1/1(4)] 4 3 [5/5(10)]
（格式：[在此处挂的装饰物个数/子树中装饰物总数(在此结点花费代价)]）
```