动态树顶点加子树求和（Dynamic Tree Vertex Add Subtree Sum）

问题描述

给定一棵含 $N$ 个顶点的树，顶点编号为 $0$ 到 $N-1$。每条边为 $(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 v p：将边 $(v, p)$ 视为有向边 $p \to v$（即 $p$ 是 $v$ 的父节点），输出以 $v$ 为根的子树中所有顶点的值之和。

注意：查询 2 v p 中，$(v, p)$ 必须是当前树中的一条边；子树定义基于将该边定向为 $p \to v$ 后，$v$ 所在的连通分支（即以 $v$ 为根、远离 $p$ 的部分）。

约束条件

• $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)$ 是当前树中的一条边
• 对 type 2 查询，$(v, p)$ 是当前树中的一条边

输入

$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 1 2
1 1 100000
2 1 2
0 1 2 2 0
2 0 2
0 2 3 3 1
2 1 4

10011
110011
110011
101111