P4315 月下“毛景树”

    • 612通过
    • 2.6K提交
  • 题目提供者 Melacau_www
  • 评测方式 云端评测
  • 标签 最近公共祖先,LCA 树链剖分,树剖 线段树
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    毛毛虫经过及时的变形,最终逃过的一劫,离开了菜妈的菜园。 毛毛虫经过千山万水,历尽千辛万苦,最后来到了小小的绍兴一中的校园里。

    爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面,发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝,但节点上是没有毛毛果的,毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力,他能改变树枝上毛毛果的个数:

    • Change k w:将第k条树枝上毛毛果的个数改变为w个。

    • Cover u v w:将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。

    • Add u v w:将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪,于是他会有如下询问:

    • Max u v:询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

    输入输出格式

    输入格式:

    第一行一个正整数N。

    接下来N-1行,每行三个正整数Ui,Vi和Wi,第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi,树枝上有Wi个毛毛果。 接下来是操作和询问,以“Stop”结束。

    输出格式:

    对于毛毛虫的每个询问操作,输出一个答案。

    输入输出样例

    输入样例#1: 复制
    4
    1 2 8
    1 3 7
    3 4 9
    Max 2 4
    Cover 2 4 5
    Add 1 4 10
    Change 1 16
    Max 2 4
    Stop
    输出样例#1: 复制
    9
    16

    说明

    1<=N<=100,000,操作+询问数目不超过100,000。

    保证在任意时刻,所有树枝上毛毛果的个数都不会超过10^9个。

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