翻译

题目描述

约翰正在装饰他家的圣诞树。圣诞树上有个 N 个结点，第一个结点是根，其余结点都有唯一的

父亲结点，第 i 个结点的父亲是 P i 。由于根没有父亲，所以记 P 1 = −1。

约翰可以在每个结点上挂载装饰物，但费用是变化。在第 i 个结点上挂载一个装饰物需要花费 C i

元钱。奶牛对这个圣诞树上每个结点都有特殊的装饰需求，对于第 i 个结点，奶牛要求以它为根的子

树上必须有 D i 个装饰物。请问约翰在哪些结点上挂载装饰物，才能满足奶牛的要求，并且使得装饰

费用最少？

输入 • 第一行：单个整数 N，1 ≤ N ≤ 10 5

• 第二行到 N 行：第 i+1 行有三个整数：P i ，D i 和 C i ，1 ≤ P i ≤ N, 0 ≤ D i ≤ 10 6 , 1 ≤ C i ≤ 100

输出 • 单个整数，表示完成所有装饰要求的最少费用

样例输入

5 -1 9 3 1 2 2 5 3 2 5 1 4 2 3 3 样例输出

20 提示 在第四个结点上放一个，花 4 元；在第三个

结点上放五个，花 10 元；在第二个结点上放三

个，花 6 元；