[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)] (格式:[在此处挂的装饰物个数/子树中装饰物总数(在此结点花费代价)]) ```

题目描述

Farmer John is decorating his Spring Equinox Tree (like a Christmas tree but popular about three months later). It can be modeled as a rooted mathematical tree with N (1 <= N <= 100,000) elements, labeled 1...N, with element 1 as the root of the tree. Each tree element e > 1 has a parent, P\_e (1 <= P\_e <= N). Element 1 has no parent (denoted '-1' in the input), of course, because it is the root of the tree. Each element i has a corresponding subtree (potentially of size 1) rooted there. FJ would like to make sure that the subtree corresponding to element i has a total of at least C\_i (0 <= C\_i <= 10,000,000) ornaments scattered among its members. He would also like to minimize the total amount of time it takes him to place all the ornaments (it takes time K\*T\_i to place K ornaments at element i (1 <= T\_i <= 100)). Help FJ determine the minimum amount of time it takes to place ornaments that satisfy the constraints. Note that this answer might not fit into a 32-bit integer, but it will fit into a signed 64-bit integer. For example, consider the tree below where nodes located higher on the display are parents of connected lower nodes (1 is the root): ```cpp For example, consider the tree below where nodes located higher on the display are parents of connected lower nodes (1 is the root): 1 | 2 | 5 / \ 4 3 Suppose that FJ has the following subtree constraints: Minimum ornaments the subtree requires | Time to install an ornament Subtree | | root | C_i | T_i --------+--------+------- 1 | 9 | 3 2 | 2 | 2 3 | 3 | 2 4 | 1 | 4 5 | 3 | 3 Then FJ can place all the ornaments as shown below, for a total cost of 20: 1 [0/9(0)] legend: element# [ornaments here/ | total ornaments in subtree(node install time)] 2 [3/9(6)] | 5 [0/6(0)] / \ [1/1(4)] 4 3 [5/5(10)] ```

输入输出格式

输入格式


\* Line 1: A single integer: N \* Lines 2..N+1: Line i+1 contains three space-separated integers: P\_i, C\_i, and T\_i

输出格式


\* Line 1: A single integer: The minimum time to place all the ornaments

输入输出样例

输入样例 #1

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

输出样例 #1

20