P2590 [ZJOI2008] Statistics on a Tree

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.

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`.

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

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