P8827 [Chuanzhi Cup #3 Preliminary] Forest

YYH Land (Yoauld, Youthful & Happy Land) is a magical country located in Chilan Xianye, where people live a free and happy life.

Qingzhengyu is a dedicated forest ranger of YYH Land. He is responsible for maintaining the forest of YYH Land every day. At the very beginning, YYH Land has only one tree with $n$ nodes, and each node has a spiritual power value $v$. Since YYH Land is a magical country, the trees in YYH Land also have some magical abilities. Specifically, the following operations are supported: - `1 e` The edge with index $e$ suddenly disappears, splitting the tree it belongs to into two trees. - `2 u val` The spiritual power value of the node with index $u$ becomes $val$. - `3 u` Qingzhengyu makes a query: find the sum of spiritual power values of the tree that contains $u$. Now you need to help Qingzhengyu simulate the events above to understand how the forest changes.

The first line contains $n, m$, as described above. The second line contains $n$ numbers, the initial weights of the $n$ nodes, each within $10^3$. The next $n - 1$ lines each contain a pair $u, v$, representing an edge. (It is guaranteed that initially it is a tree.) The next $m$ lines contain $m$ operations: First read an $opt$, indicating the operation type. When $opt = 1$, read $e$, meaning to delete the $e$-th input edge. (It is guaranteed that the $e$-th edge exists.) When $opt = 2$, read $u, val$, meaning to change the weight of node $u$ to $val$ ($val \le 1000$). When $opt = 3$, read $u$, meaning to query the sum of node weights in the tree that contains $u$.

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

For $30\%$ of the testdata, $1 \leq n, m \leq 10$ holds. For $50\%$ of the testdata, $1 \leq n, m \leq 1000$ holds. For the other $20\%$ of the testdata, only operations $2$ and $3$ exist. For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, and $1 \leq v, val \leq 1000$ hold. Translated by ChatGPT 5