Tree Statistics

Problem Source

ZJOI 2008

Problem Description

There is a tree with $n$ nodes numbered $1$ to $n$, each node carrying a weight $w$. You must support the following operations on the tree:

1. CHANGE u t: change the weight of node $u$ to $t$.
2. QMAX u v: query the maximum weight among the nodes on the path from $u$ to $v$.
3. QSUM u v: query the sum of weights of the nodes on the path from $u$ to $v$. (The path from $u$ to $v$ includes both $u$ and $v$ themselves.)

Input Format

The first line of the input 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 $n$ lines each contain one integer; the $i$-th line contains $w_i$, the weight of node $i$.

Then one line contains an integer $q$, the total number of operations.

The next $q$ lines each describe one operation, given in the form CHANGE u t, QMAX u v, or QSUM u v.

It is guaranteed that $1 \leq n \leq 3 \times 10^4,\ 0 \leq q \leq 2 \times 10^4$, and that during the operations every node weight $w$ remains between $-3 \times 10^4$ and $3 \times 10^4$.

Output Format

For each QMAX or QSUM operation, output one integer per line: the requested result.

Sample Input

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

Sample Output

4
1
2
2
10
6
5
6
5
16

Constraints

• $1 \leq n \leq 3 \times 10^4$
• $0 \leq q \leq 2 \times 10^4$
• $-3 \times 10^4 \leq w \leq 3 \times 10^4$