동적 트리 정점 더하기 경로 합

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

다음 $Q$개의 질의를 순서대로 처리하여라. 질의를 처리하는 동안 그래프는 항상 트리이다.

• 0 $u\ v\ w\ x$: 현재 존재하는 간선 $(u,v)$를 삭제하고, 간선 $(w,x)$를 추가한다.
• 1 $p\ x$: 로 바꾼다.

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

$N\ Q$ $a_0\ a_1\ \cdots\ a_{N-1}$

각 2번 질의마다, 현재 트리에서 해당 경로 위 정점값의 합을 한 줄에 하나씩 출력한다.

• $1 \leq N,Q \leq 200\ 000$.
• $0 \leq a_i \leq 10^9$ ().