#326 Dynamic Tree Vertex Add Path Sum

Statement

$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 $u\ v$ : 현재 트리에서 $u$ 번 정점과 $v$ 번 정점을 잇는 단순 경로 위의 모든 정점값의 합을 출력한다. 양 끝 정점도 포함한다.

Input

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

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

각 $i$ ( $0 \leq i \leq N-2$ )에 대해 처음 트리에는 $u_i$ 번 정점과 $v_i$ 번 정점을 잇는 간선이 있다.

Output

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

Constraints

$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$ ).
처음 주어지는 $N-1$ 개의 간선은 트리를 이룬다.
0번 질의에서 $0 \leq u,v,w,x < N$ 이고, 질의 직전에 간선 $(u,v)$ 가 존재한다. 간선 $(u,v)$ 를 삭제하고 간선 $(w,x)$ 를 추가한 뒤에도 그래프는 트리이다.
1번 질의에서 $0 \leq p < N$ 이고 $0 \leq x \leq 10^9$ 이다.
2번 질의에서 $0 \leq u,v < N$ 이다.
입력으로 주어지는 모든 수는 정수이다.

Subtasks

#	Score	Constraints
1	18	$N,Q \leq 200$ .
2	20	`0`번 질의가 없다.
3	24	$N,Q \leq 5000$ .
4	38	추가적인 제약조건이 없다.

Samples

Input

7
10 100 1000 10000
1
2
3
4
0 3
1 100000
3 4
1 2 2 0
3 4
2 3 3 1
2 3

Output

처음 정점값은 $1,10,100,1000,10000$ 이다.

첫 번째 출력은 경로 $0-1-2-3$ 의 합 $1+10+100+1000=1111$ 이다.

그 뒤 $1$ 번 정점의 값이 $100010$ 이 된다. 두 번째 출력은 경로 $3-2-1-4$ 의 합 $1000+100+100010+10000=111110$ 이다.

간선 $(1,2)$ 를 삭제하고 $(2,0)$ 을 추가한 뒤, 세 번째 출력은 경로 $3-2-0-1-4$ 의 합 $111111$ 이다.

간선 $(2,3)$ 을 삭제하고 $(3,1)$ 을 추가한 뒤, 마지막 출력은 경로 $2-0-1-3$ 의 합 $101111$ 이다.

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

Statement

Input

Output

Constraints

Subtasks

Samples