点加路径求和

【题目描述】

给定一棵 $N$ 个顶点的树，边为 $(u_i, v_i)$ 。顶点 $i$ 上写有数值 $a_i$ 。

依次处理以下 $Q$ 个查询：

0 $p$ $x$： $a_p \gets a_p + x$
1 $u$ $v$：输出顶点 $u$ 与顶点 $v$ 之间路径上（含两端）所有顶点的数值之和。

【输入】

输入格式如下：

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$u_0$ $v_0$
$u_1$ $v_1$
:
$u_{N - 2}$ $v_{N - 2}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

【输出】

对每个 1 $u$ $v$ 查询，输出一行一个整数，表示顶点 $u$ 与顶点 $v$ 之间路径上（含两端）所有顶点的数值之和。

【输入样例】

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

【输出样例】

【数据范围】

$1 \leq N, Q \leq 500000$
$0 \leq a_i, x \leq 1000000000$
$0 \leq p, u_i, v_i < N$

【来源】

Library Checker（yosupo06） vertex_add_path_sum