动态树子树加子树求和（Dynamic Tree Subtree 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 v p x：将边 $(v, p)$ 视为父边（即 $p$ 是 $v$ 的父节点），对以 $v$ 为根的子树中所有顶点的值加上 $x$。
• 2 v p：将边 $(v, p)$ 视为父边（即 $p$ 是 $v$ 的父节点），输出以 $v$ 为根的子树中所有顶点的值之和。

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

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq a_i \leq 10^7$
• $0 \leq u, v, w, x < N$
• $0 \leq x \leq 10^7$
• 图始终为树；对类型 0 查询，$(u,v)$ 存在；对类型 1/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 0
1 1 4 100000
2 2 3
0 1 2 2 0
2 0 2
0 2 3 3 1
2 1 4

11110
310111
210011
401111