Tree Decoration

题号：NC24623
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

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

               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: , , and

输出描述:

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

示例1

输入

复制

输出

复制