动态树点加路径求和

【题目描述】

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

依次处理以下 $Q$ 个查询。可以假设在处理查询的过程中，图始终是一棵树。

• 0 $u$ $v$ $w$ $x$：删除一条边 $(u, v)$，并添加 $(w, x)$。
• 1 $p$ $x$：$a_p \gets a_p + x$
• 2 $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}$

【输出】

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

【输入样例】

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

【输出样例】

1111
111110
111111
101111

【数据范围】

• $1 \leq N, Q \leq 200,000$
• $0 \leq a_i, x \leq 10^9$
• $0 \leq p, u_i, v_i < N$
• $(u_i, v_i)$ 构成一棵树。
• 对于类型 0 的查询，存在边 $(u, v)$。
• 图始终是树。

【来源】

Library Checker（yosupo06） dynamic_tree_vertex_add_path_sum