#3838. 月下“毛景树”

月下“毛景树”

月下“毛景树”

题目背景

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

题目描述

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

  • Change k w:将第k条树枝上毛毛果的个数改变为 ww 个。
  • Cover u v w:将节点 uu 与节点 vv 之间的树枝上毛毛果的个数都改变为 ww 个。
  • Add u v w:将节点 uu 与节点 vv 之间的树枝上毛毛果的个数都增加 ww 个。

由于毛毛虫很贪,于是他会有如下询问:

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

输入格式

第一行一个正整数 NN

接下来 N1N-1 行,每行三个正整数 Ui,ViU_i,V_iWiW_i,第 i+1i+1 行描述第 ii 条树枝。表示第 ii 条树枝连接节点 UiU_i 和节点 ViV_i,树枝上有 WiW_i 个毛毛果。 接下来是操作和询问,以 Stop 结束。

输出格式

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

样例 #1

样例输入 #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

提示

对于全部数据,1N1051\le N\le 10^5,操作和询问数目不超过 10510^5

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