蓝桥守护者 ### 题目描述 传说蓝桥王国有一棵神树——蓝桥树。 蓝桥树包含 $N$ 个节点，编号分别为 $1 \sim N$，起初第 $i$ 个节点有 $a_i$ 的魔力，根节点为 $1$。 蓝桥国王每年都会选出一名蓝桥守护者，来守护蓝桥树。而今年，小明被选中成为了蓝桥守护者。 蓝桥树是有生命的，每年它都会向守护者布置 $Q$ 个任务，任务有以下 $4$ 种类型： + `1 u v w`，将节点 $u$ 到节点 $v$ 最短路径上的所有节点的魔力值加上 $w$。 + `2 u w`，将以节点 $u$ 为根的子树的所有节点的魔力值加上 $w$。 + `3 u v `，计算并告知蓝桥树从节点 $u$ 到节点 $v$ 最短路径上的所有节点的魔力值之和。 + `4 u`，计算并告知蓝桥树以节点 $u$ 为根的子树的所有节点的魔力值之和。 若不能顺利完成任务，蓝桥树将予以守护者可怕的惩罚。 刚当选蓝桥守护者的小明并不知道该如何完成任务，于是他希望作为上一届蓝桥守护者的你能帮他完成任务。 ### 输入描述 输入第 $1$ 行包含一个正整数 $N$，表示蓝桥树的节点个数 第 $2$ 行包含 $N$ 个非负整数 $a_1,a_2,...,a_N$，分别表示节点 $1\sim N$ 的初始魔力值。 第 $3\sim N+1$ 行每行包含两个正整数 $u,v$，表示 $u\leftrightarrow v$ 之间存在一条边。 第 $3$ 行包含一个正整数 $Q$，表示蓝桥树布置的任务个数。 接下来的 $Q$ 行，每行输入一个操作，形如： + `1 u v w` + `2 u w` + `3 u v ` + `4 u` 含义如题所述。 $1\leq N \leq 10^5$，$1 \leq Q \leq10^5$，$1 \leq u, v\leq N$，$-10^9\leq w,a_i\leq 10^9$。 ### 输出描述 对于操作 $3$、操作 $4$，输出对应的计算结果来告诉蓝桥树。 ### 输入输出样例 #### 示例 1 >输入 ```txt 5 1 2 3 4 5 1 2 1 3 1 4 2 5 5 3 2 5 1 2 5 3 3 2 5 2 1 1 4 1 ``` >输出 ```txt 7 13 26 ```