트리에서 정점 가산 범위 등고선 합

$N$개의 정점으로 이루어진 트리가 주어지며, $i$번째 간선은 정점 $u_i$와 $v_i$을 연결한다. 정점 $i$에는 값 $a_i$이 쓰여 있다. 다음 $Q$개의 쿼리를 순서대로 처리한다:

• 0 $p$ $x$: $a_p \leftarrow a_p+x$
• 1 $p$ $l$ $r$: 정점 $p$으로부터의 거리가 $[l,r)$에 속하는 정점들에 쓰인 값의 합을 출력한다.

제약 조건

• $1 \leq N \leq 100000$
• $1 \leq Q \leq 200000$
• $-1000000000 \leq a_i \leq 1000000000$
• $0 \leq u_i, v_i \leq N-1$
• $0 \leq p \leq N-1$
• $-1000000000 \leq x \leq 1000000000$
• $0 \leq l \lt r \leq N$

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

1 $p$ $l$ $r$: 정점 $p$으로부터의 거리가 $[l,r)$에 속하는 정점들에 쓰인 값의 합을 출력한다.