该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

动态树点修 & 路径求和（Dynamic Tree Vertex Add Path Sum）

问题描述

给定一棵含 $N$ 个顶点的树，初始时每条边为 $(u_i, v_i)$，顶点 $i$ 上的值为 $a_i$。
处理 $Q$ 个查询，类型如下：

• 0 u v w x：删除边 $(u, v)$，并添加新边 $(w, x)$（保证操作后仍为树）。
• 1 p x：将顶点 $p$ 的值更新为 $a_p \leftarrow a_p + x$。
• 2 u v：输出从 $u$ 到 $v$ 的简单路径上所有顶点的值之和（含端点 $u$ 和 $v$）。

注：题目说明“the graph is always tree”，且对 type 0 查询，“there is an edge $(u, v)$”，即删除前该边存在。

约束条件

• $1 \leq N, Q \leq 200\,000$
• $0 \leq a_i, x \leq 10^9$
• $0 \leq p, u, v, w, x < N$
• 边 $(u_i, v_i)$ 构成一棵树
• 对 type 0 查询，$(u, v)$ 是当前树中的一条边

输入

$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₀
Query₁
:
Query$_{Q-1}$

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