P3018 [USACO11MAR]树装饰Tree Decoration

    • 115通过
    • 267提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2011
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    约翰正在装饰他家的圣诞树。圣诞树上有个 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 元;

    感谢@lushangyin 提供的翻译

    题目背景

    征求翻译。如果你能提供翻译或者题意简述,请直接发讨论,感谢你的贡献。

    题目描述

    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: 复制
    5 
    -1 9 3 
    1 2 2 
    5 3 2 
    5 1 4 
    2 3 3 
    
    输出样例#1: 复制
    20 
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。