维护计划

题目描述

Y 同学拥有一棵包含 $N$ 个节点的“毛景树”，树上有 $N-1$ 条树枝连接着这些节点，使得所有节点连通。毛毛果仅生长在树枝上，每条树枝初始时都具有一定数量的毛毛果。

为了更好地管理这些毛毛果，Y 同学需要执行以下四种操作：

• Change k w：将第 $k$ 条输入的树枝上毛毛果的数量修改为 $w$。
• Cover u v w：将节点 $u$ 与节点 $v$ 之间简单路径上所有树枝的毛毛果数量均修改为 $w$。
• Add u v w：将节点 $u$ 与节点 $v$ 之间简单路径上所有树枝的毛毛果数量均增加 $w$。
• Max u v：查询节点 $u$ 与节点 $v$ 之间简单路径上所有树枝中，毛毛果数量的最大值。

请你编写一个程序，帮助 Y 同学高效地处理这些操作。

输入格式

第一行包含一个整数 $N$，表示节点的数量。

接下来 $N-1$ 行，每行包含三个整数 $U_i, V_i$ 和 $W_i$，表示第 $i$ 条输入的树枝连接节点 $U_i$ 和 $V_i$，且初始时拥有 $W_i$ 个毛毛果。

接下来是若干行操作指令，每行代表一个操作。指令格式详见题目描述。 当读取到字符串 Stop 时，表示操作结束。

输出格式

对于每一个 Max 询问，输出一行一个整数，表示对应路径上毛毛果数量的最大值。

样例

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

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 10^5$，操作总数不超过 $10^5$。 在任意时刻，任意树枝上的毛毛果数量均在 $[0, 10^9]$ 范围内。 所有输入的 $u, v, k$ 以及权值 $w$ 均满足题目描述的要求且在合法范围内。

特殊性质 A：保证给定的树是一条链。 特殊性质 B：保证不存在 Cover 修改操作。