Background

Ray loves traveling, and this time he has arrived in T City. T City is a city of waterways with $n$ attractions, and some pairs of attractions are connected by a bridge. To make it easy for tourists to reach every attraction while saving costs, there is exactly one path between any two attractions. In other words, there are only $n-1$ bridges in T City.

Ray noticed that some bridges offer beautiful scenery that lifts the mood, while others are narrow and muddy, which is frustrating. So he assigns a pleasure value $w$ to each bridge, meaning Ray’s pleasure increases by $w$ when he crosses that bridge, which could be positive or negative. Sometimes, Ray’s feelings about the same bridge also change.

Now, Ray wants you to help him compute the total pleasure he can get when traveling from attraction $u$ to attraction $v$. Sometimes he also wants to know the maximum pleasure provided by the most beautiful bridge on a certain route, or the minimum pleasure provided by the worst bridge on a certain route.

Problem Description

You are given a tree with $n$ nodes, edges have weights, and nodes are numbered $0 \sim n-1$. You need to support five operations. Edges are indexed by their input order from $1$ to $n-1$.

• C i w Change the weight of the $i$-th edge in the input to $w$.
• N u v Negate the weights of all edges on the path between $u$ and $v$.
• SUM u v Query the sum of edge weights on the path between $u$ and $v$.
• MAX u v Query the maximum edge weight on the path between $u$ and $v$.
• MIN u v Query the minimum edge weight on the path between $u$ and $v$.

At any time, all edge weights are within $[-1000, 1000]$.

Input Format

The first line contains a positive integer $n$, the number of nodes. The next $n-1$ lines each contain three integers $u, v, w$, indicating that there is an edge between $u$ and $v$ with weight $w$, describing the tree. Then a line with a positive integer $m$, the number of operations. The next $m$ lines each describe one operation.

Output Format

For each query operation, output one line with one integer representing the answer.

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2

3
2
1
-1
5
3

Hint

Constraints

For $100\%$ of the testdata, $1 \le n, m \le 2 \times 10^5$.

2020.02.04 Fixed a small error in the testdata. 2020.03.14 Added a set of hack testdata. 2020.11.26 Added a set of hack testdata by @_Leaving.

Translated by ChatGPT 5