Description

There is a tree with $n$ nodes, numbered from $1$ to $n$, and each node has a weight $w$.

You are asked to perform the following operations on the tree:

I. CHANGE u t: Set the weight of node $u$ to $t$.

II. QMAX u v: Query the maximum weight among the nodes on the path from $u$ to $v$.

III. QSUM u v: Query the sum of the weights of the nodes on the path from $u$ to $v$.

Note: The nodes on the path from $u$ to $v$ include $u$ and $v$ themselves.

Input Format

The first line contains an integer $n$, the number of nodes.

The next $n-1$ lines each contain two integers $a$ and $b$, indicating that there is an edge between node $a$ and node $b$.

The next line contains $n$ integers, where the $i$-th integer $w_i$ is the weight of node $i$.

The next line contains an integer $q$, the total number of operations.

The next $q$ lines each contain one operation, given as CHANGE u t, QMAX u v, or QSUM u v.

Output Format

For each QMAX or QSUM operation, output one integer on its own line representing the result.

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

4
1
2
2
10
6
5
6
5
16

Hint

Constraints:

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 3\times 10^4$ and $0 \le q \le 2\times 10^5$.

Throughout the operations, each node’s weight $w$ is guaranteed to be between $-3\times 10^4$ and $3\times 10^4$.

Translated by ChatGPT 5