#980. 1984. 月下“毛景树”

1984. 月下“毛景树”

#1984. 月下“毛景树”

题目描述

毛毛虫经过及时的变形,最终逃过的一劫,离开了菜妈的菜园。 毛毛虫经过千山万水,历尽千辛万苦,最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬毛毛虫爬到了一颗小小的"毛景树"下面,发现树上长着他最爱吃的毛毛果~ "毛景树"上有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"结束。

输出格式

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

样例

样例输入

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

样例输出

9  
16

【Data Range】

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

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

数据范围与提示