动态树子树加子树求和

【题目描述】

给定一棵有 $N$ 个顶点的树。第 $i$ 条边连接顶点 $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$ 的子树中所有顶点的值加上 $x$。
• 2 $v$ $p$：以边 $(v, p)$ 为参照，把 $p$ 看作父亲，求顶点 $v$ 的子树中所有顶点的值之和。

【输入】

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$u_0$ $v_0$
$u_1$ $v_1$
$\hspace{11pt} \vdots$
$u_{N - 2}$ $v_{N - 2}$
$\mathrm{Query}_0$
$\mathrm{Query}_1$
$\hspace{14pt} \vdots$
$\mathrm{Query}_{Q - 1}$

【输出】

对每个 2 $v$ $p$ 类型的查询，输出一行一个整数，表示所求的和。

【输入样例】

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

【数据范围】

• $2 \le N \le 200000$
• $1 \le Q \le 200000$
• $0 \le a_i \le 10000000$
• $0 \le u_i, v_i < N$
• 该图是一棵树
• 对于 0 $u$ $v$ $w$ $x$ 类型的查询：
  • $0 \le u, v, w, x \lt N$
  • 处理该类型的查询时，边 $(u, v)$ 存在
  • 处理之后该图仍然是一棵树
• 对于 1 $v$ $p$ $x$ 类型的查询：
  • $0 \le v, p \lt N$
  • $0 \le x \le 10000000$
  • 处理该类型的查询时，边 $(v, p)$ 存在
• 对于 2 $v$ $p$ 类型的查询：
  • $0 \le v, p \lt N$
  • 处理该类型的查询时，边 $(v, p)$ 存在

【来源】

Library Checker（yosupo06） dynamic_tree_subtree_add_subtree_sum