B. 树的装饰

    传统题 1000ms 256MiB

树的装饰

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

给定一颗以 11 为根的有根树,第 ii 个结点的父结点为 PiP_i(P1=−1P_1=-1),在第 ii 个结点上挂一个装饰物的代价为 TiT_i,每个结点可以挂任意个。现在给定每棵树子树中至少挂的装饰物个数 CiC_i,求满足要求的最少花费。

输入格式

第一行:一个整数 nn。

接下来 nn 行:每行三个整数,分别表示 PiP_i,CiC_i 和 TiT_i。

输出格式

一行一个整数表示最小花费。

样例输入

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

样例输出

20 

样例解释

样例中给出的树如下:
               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)]

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

数据范围

1≤n≤1051 \leq n \leq 10^5,1≤Ti≤1001 \leq T_i \leq 100,1≤Ci≤1071 \leq C_i \leq 10^7。

2026-11-14

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-11-14 7:30
结束于
2026-11-14 12:00
持续时间
4.5 小时
主持人
参赛人数
14