P3787 冰精冻西瓜

    • 58通过
    • 286提交
  • 题目提供者 orangebird
  • 评测方式 云端评测
  • 标签 树状数组 模拟 线段树 洛谷原创 Special Judge
  • 难度 提高+/省选-
  • 时空限制 900ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    盛夏,冰之妖精琪露诺发现了一大片西瓜地,终于可以吃到美味的冻西瓜啦。

    题目描述

    琪露诺是拥有操纵冷气程度的能力的妖精,一天她发现了一片西瓜地。这里有n个西瓜,由n-1条西瓜蔓连接,形成一个有根树,琪露诺想要把它们冷冻起来慢慢吃。

    这些西瓜蔓具有神奇的性质,可以将经过它的冷气的寒冷程度放大或缩小,每条西瓜蔓放大/缩小冷气寒冷程度的能力值为Wi,表示冷气经过它后,寒冷程度值x会变为x*wi。每个西瓜也有一个寒冷程度值,炎热的夏日,所有西瓜的寒冷程度值初始都为0。

    琪露诺会做出两种动作:

    ①.对着西瓜i放出寒冷程度为x的冷气。这股冷气顺着西瓜蔓向“西瓜树”的叶子节点蔓延,冷气的寒冷程度会按照上面的规则变化。遇到一个西瓜连了多条西瓜蔓时,每条叶子节点方向的西瓜蔓均会获得与原先寒冷程度相等的冷气。途径的所有西瓜的寒冷程度值都会加上冷气的寒冷程度值。

    ⑨.向你询问西瓜i的寒冷程度值是多少。

    等等,为什么会有⑨?因为笨蛋琪露诺自己也会忘记放了多少冰呢。

    所以,帮她计算的任务就这么交给你啦。

    输入输出格式

    输入格式:

    第一行一个整数n,表示西瓜的数量。

    西瓜编号为1~n,1为这棵“西瓜树”的根。

    接下来n-1行,每行有两个整数u,v和一个实数w,表示西瓜u和西瓜v之间连接有一条藤蔓,它放大/缩小冷气寒冷程度的能力值为w。

    接下来一行一个整数m,表示操作的数量。

    接下来m行,每行两个或三个整数。

    第一个数只能是1或9。

    如果为1,接下来一个整数i和一个实数x,表示对西瓜i放出寒冷程度为x的冷气。

    如果为9,接下来一个整数i,表示询问编号为i的西瓜的寒冷程度值。

    输出格式:

    对于每个操作⑨,输出一行一个实数,表示对应西瓜的寒冷程度值。

    输入输出样例

    输入样例#1: 复制
    4
    1 2 1.00000000
    2 3 0.00000000
    3 4 1.00000101
    9
    1 1 3.00000000
    9 2
    9 3
    1 2 1.42856031
    9 4
    9 2
    1 3 4.23333333
    9 2
    9 4
    输出样例#1: 复制
    3.00000000
    0.00000000
    0.00000000
    4.42856031
    4.42856031
    4.23333761

    说明

    子任务可能出现如下的特殊性质:

    “西瓜树”退化为一条链

    输入数据中的实数均保留8位小数,选手的答案被判作正确当且仅当输出与标准答案误差不超过10^-7。请特别注意浮点数精度问题。

    实际数据中,冷气的寒冷程度x的范围为 [-0.1,0.1]

    (样例中的冷气寒冷程度的范围为[1,5])

    命题人:orangebird,鸣谢oscar。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。