顶点加路径和（Vertex Add Path Sum）

问题描述

给定一棵含 $N$ 个顶点的树，边为 $(u_i, v_i)$。每个顶点 $i$ 上初始写有值 $a_i$。
请按顺序处理以下 $Q$ 个查询：

• 0 p x：将顶点 $p$ 上的值增加 $x$（即 $a_p \leftarrow a_p + x$）。
• 1 u v：输出从顶点 $u$ 到顶点 $v$ 的简单路径上所有顶点的值之和（包含端点 $u$ 和 $v$）。

约束条件

• $1 \leq N, Q \leq 5 \times 10^5$
• $0 \leq a_i, x \leq 10^9$
• $0 \leq p, u, v < N$

输入格式

$N\ Q$
$a_0\ a_1\ \cdots\ a_{N-1}$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{N-2}\ v_{N-2}$
$Query_0$
$Query_1$
:
$Query_{Q-1}$

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

1111
10110
101110
1100