동적 트리 정점 더하기 서브트리 합

$N$개의 정점으로 이루어진 트리가 주어진다. 정점은 $0,1,\cdots,N-1$번으로 번호가 붙어 있으며, 처음에 $i$번 정점에는 값 $a_i$가 적혀 있다.

다음 $Q$개의 질의를 순서대로 처리하여라. 모든 질의를 처리하는 동안, 각 질의가 끝난 뒤의 그래프는 항상 트리임이 보장된다.

• 0 $u$ $v$ $w$ $x$: 현재 존재하는 간선 $(u,v)$를 삭제하고, 간선 $(w,x)$를 추가한다.
• 1 $p$ $x$: $a_p \leftarrow a_p+x$로 값을 갱신한다.
• 2 $v$ $p$: 현재 존재하는 간선 $(v,p)$에서 $p$를 $v$의 부모 쪽 정점으로 본다. 이 간선을 제거했을 때 $v$가 속한 연결 컴포넌트에 있는 모든 정점의 값의 합을 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$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$는 처음 트리의 $i$번 간선을 나타낸다. 각 질의는 문제 설명에 나온 세 형식 중 하나로 주어진다.

2번 질의마다, 요구한 정점 값의 합을 한 줄에 하나씩 출력한다.

• $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$).
• 처음 주어지는 간선들은 트리를 이룬다.
• 0번 질의에서 삭제하는 간선 $(u,v)$는 현재 존재한다.
• 0번 질의가 끝난 뒤 그래프는 트리이다.
• 1번 질의에서 $0 \leq p < N$, $0 \leq x \leq 10^9$이다.
• 2번 질의에서 간선 $(v,p)$는 현재 존재한다.