月下“毛景树”
题目背景
毛毛虫经过及时的变形,最终逃过的一劫,离开了菜妈的菜园。 毛毛虫经过千山万水,历尽千辛万苦,最后来到了小小的绍兴一中的校园里。
题目描述
爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面,发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有 $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$ 行,每行三个正整数 $U_i,V_i$ 和 $W_i$,第 $i+1$ 行描述第 $i$ 条树枝。表示第 $i$ 条树枝连接节点 $U_i$ 和节点 $V_i$,树枝上有 $W_i$ 个毛毛果。 接下来是操作和询问,以 `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\le N\le 10^5$,操作和询问数目不超过 $10^5$。
保证在任意时刻,所有树枝上毛毛果的个数都不会超过 $10^9$ 个。