Dynamic Tree Vertex Add Path Sum

You are given a tree with $N$ vertices. The vertices are numbered $0,1,\cdots,N-1$, and initially vertex $i$ has an integer value $a_i$.

Process the following $Q$ queries in order. The graph is always a tree while the queries are processed.

• 0 $u\ v\ w\ x$: delete the existing edge $(u,v)$ and add the edge $(w,x)$.
• 1 $p\ x$: replace $a_p$ with $a_p+x$.
• 2 $u\ v$: print the sum of the values of all vertices on the simple path from vertex $u$ to vertex $v$ in the current tree, including both endpoints.

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}$

For each $i$ ($0 \leq i \leq N-2$), the initial tree has an edge connecting vertices $u_i$ and $v_i$.

For each query of type 2, print one line containing the sum of the values of the vertices on the specified path in the current tree.

• $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 $N-1$ edges form a tree.
• In a query of type 0, $0 \leq u,v,w,x < N$, and the edge $(u,v)$ exists immediately before the query. After deleting $(u,v)$ and adding $(w,x)$, the graph is still 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, $0 \leq u,v < N$.
• All numbers in the input are integers.