Problem Description

Little A arrives at the foot of a mountain and plans to build a small house. At this moment, Little A’s friend (op, also called the administrator) turns on Creative Mode, flies to the top of the mountain, and places a block of water. Then a waterfall appears in front of Little A. As an ordinary player, Little A has to climb the mountain and block the water.

Now here is the problem: we view this waterfall as a tree with $n$ nodes, where the root is $1$. Each node has a weight (the cost to climb up to it). Little A wants to choose some nodes and delete (block) them, paying the sum of their weights as the cost, so that the root node is disconnected from all leaf nodes. Find the minimum cost.

But it is not over yet. Little A’s friend thinks this is too cheap for Little A, so he will keep modifying the terrain, causing the weight of some node to change.

But it is still not over. Little A feels his friend has gone too far, so he gives up on separating all leaf nodes. Instead, each time he only needs to do this within a certain subtree (and it is completely unrelated to nodes outside that subtree). So he comes to you for help.

Input Format

The first line contains an integer $n$, denoting the size of the tree.

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

The next $n - 1$ lines each contain two integers $fr,to$, indicating that there is an edge $(fr,to)$ in the tree.

The next line contains an integer $m$, denoting the number of operations.

The next $m$ lines each describe an operation. If the first character is Q, it is a query operation, followed by one parameter $x$, meaning the root of the queried subtree. If it is C, it is a modify operation, followed by two parameters $x,t$, meaning to add $t$ to the weight of node $x$.

Output Format

For each query operation, output the corresponding answer. Print each answer on its own line.

4
4 3 2 1
1 2
1 3
4 2
4
Q 1
Q 2
C 4 10
Q 1

3
1
4

Hint

Constraints: $1 \leq n \leq 200000$, $1 \leq fr,to \leq n$, $1 \leq x \leq n$. The weights and $t$ are both within the int range and are non-negative.

BZOJ4712.

Translated by ChatGPT 5