Farmer John is decorating his Spring Equinox Tree (like a Christmastree but popular about three months later). It can be modeled as arooted mathematical tree with N (1 <= N <= 100,000) elements, labeled1...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 ofthe tree.

Each element i has a corresponding subtree (potentially of size 1)rooted there. FJ would like to make sure that the subtree correspondingto 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 placeornaments that satisfy the constraints. Note that this answer mightnot 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: P_i, C_i, and T_i

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

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

20

题目分析：

简单树形DP 维护一下子树最小值 和子树的size 注意一下细节就可以了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int head[100100],next[200200],to[200200];
int tot;
void add(int x,int y)
{
    next[++tot]=head[x];
    to[tot]=y;
    head[x]=tot;
}
long long minn[100100],sum[100100],c[100100],t[100100];
long long ans;
void dfs(int x,int temp)
{
    minn[x]=c[x];
    for(int i=head[x];i;i=next[i])
    {
        if(to[i]==temp) continue;
        dfs(to[i],x);
        minn[x]=min(minn[x],minn[to[i]]);
        sum[x]+=sum[to[i]];
    }
    if(t[x]>sum[x]) ans+=(t[x]-sum[x])*minn[x],sum[x]=T[x];
}
int fa;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d%d%d",&x,&t[i],&c[i]);
        if(x==-1) x=0;
        add(x,i),add(i,x);
    }
    dfs(0,-1);
    printf("%lld",ans);
    return 0;
}