题目描述

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):

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$ 为根的有根树，第 $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)]

（格式：[在此处挂的装饰物个数/子树中装饰物总数(在此结点花费代价)]）

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

20