Dynamic Tree Vertex Add Subtree Sum

You are given a tree with $N$ vertices numbered $0,1,\cdots,N-1$. Initially, vertex $i$ has value $a_i$.

Process $Q$ queries in order. It is guaranteed that after each query, the graph is a tree.

• 0 $u$ $v$ $w$ $x$: remove the existing edge $(u,v)$, and add the edge $(w,x)$.
• 1 $p$ $x$: update $a_p \leftarrow a_p+x$.
• 2 $v$ $p$: for the current edge $(v,p)$, regard $p$ as the parent side of $v$. Output the sum of values of all vertices in the connected component containing $v$ after removing this edge.

The input is given in the following format.

$N\ Q$ $a_0\ a_1\ \cdots\ a_{N-1}$ $u_0\ v_0$ $u_1\ v_1$ $\vdots$ $u_{N-2}\ v_{N-2}$ $\mathrm{Query}_0$ $\mathrm{Query}_1$ $\vdots$ $\mathrm{Query}_{Q-1}$

$u_i,v_i$ denote the $i$-th edge of the initial tree. Each query is given in one of the three formats described in the statement.

For each query of type 2, print the required sum of vertex values on a separate line.

• $1 \leq N,Q \leq 200\ 000$.
• $0 \leq a_i \leq 10^9$ ($0 \leq i < N$).
• $0 \leq u_i,v_i < N$ ($0 \leq i \leq N-2$).
• The initially given edges form a tree.
• In a query of type 0, the removed edge $(u,v)$ currently exists.
• After each query of type 0, the graph is a tree.
• In a query of type 1, $0 \leq p < N$ and $0 \leq x \leq 10^9$.
• In a query of type 2, the edge $(v,p)$ currently exists.