一棵有 N 个节点的树,共 N - 1 条树枝,每条树枝上有若干毛毛果。需要支持以下操作: 1.Change k w:将第 k 条树枝上的毛毛果个数改为 w。 2.Cover u v w:将结点 u 到结点 v 路径上所有树枝的毛毛果个数都改为 w。 3.Add u v w:将结点 u 到结点 v 路径上所有树枝的毛毛果个数都增加 w。 4.Max u v:询问结点 u 到结点 v 路径上树枝毛毛果个数的最大值。
第一行一个正整数 N。 接下来 N - 1 行,每行三个正整数 Ui、Vi、Wi,描述第 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
1 ≤ N ≤ 100000,操作和询问总数不超过 100000。任意时刻所有树枝上毛毛果个数不超过 10^9。