Andeviking开公司 (hard)

描述

（本题与 easy 版本的不同之处仅仅在 $N$ 与 $Q$ 数据范围，并保证 easy 版的测试数据是 hard 版的测试数据的子集。若你的程序能通过 hard 版，则它同样可以通过 easy 版）

Andeviking 受够了打工人的生活。为了体验一下老板的感觉，他准备自己开一家公司，而一个公司能够高效运转的前提是该公司有一个高效的财务系统。由于 Andeviking 难以接受市面上现有系统的低效，他想让你这个水平高超的 acmer 帮他设计一套财务系统。

公司的人员按照职位高低可以构成一棵有根树，其中 1 号节点为根节点。每个节点的子节点可以看作是该节点的员工，每个节点也可以被看作是该节点的子节点的上司。每个人能且仅能修改自己员工的工资（他当然不可以自己给自己发工资）。每个人在公司中的等级定义为他上司的个数（上司的个数可以看作该点在树上的深度，其中 1 号节点的深度为 0），每人的初始工资将由输入给出。该财务系统需要支持以下五种操作：

• $1$ $p$ $x$：将编号为 $p$ 的人的工资改为 $x$ $({-10^6} \leq x \leq {10^6})$
• $2$ $p$ $k$ $x$：编号为 $p$ 的人将自己员工中比他恰好低 $k$ ($1 \le k \leq 10^6$)级的员工的工资全部改为 $x$ $({-10^6} \leq x \leq {10^6})$，若不存在这样的员工，则忽略此次操作
• $3$ $p$ $k$ $x$：编号为 $p$ 的人将自己员工中比他恰好低 $k$ ($1 \le k \leq 10^6$)级的员工的工资全部增加或减少 $x$ $({-10^6} \leq x \leq {10^6})$，正数代表增加，负数代表减少，0 代表不变，若不存在这样的员工，则忽略此次操作
• $4$ $p$：查询编号为 $p$ 的人的工资
• $5$ $p$ $k$：查询编号为 $p$ 的人的员工中比他恰好低 $k$ ($1 \le k \leq 10^6$)级的员工的工资和，若不存在这样的员工，输出 0

（请不要惊讶于工资可以是负数，作为一位凉心资本家，Andeviking 这样做是很正常的）

Andeviking 的耐心是有限的，他希望你在五小时内设计出满足要求的系统，作为报酬他会让志愿者送你一个气球。作为一个强大的 acmer ，请你帮帮 Andeviking 吧。

输入数据

第一行一个正整数 $N$，代表公司中人员数量 $(2 \leq N \leq {10^5})$

第二行 $N$ 个整数 $a_1 , a_2,\cdots,a_N$，表示编号为 $i$ 的人的初始工资为 $a_i$ $({-10^6} \leq a_i \leq {10^6})$

接下来 $N-1$ 行，每行两个正整数 $u , v$ 表示在有根树中 $u,v$ 之间存在一条边 $(1 \leq u,v \leq N)$

接下来一个正整数 $Q$，代表查询的次数 $(1 \leq Q \leq {10^5})$

接下来 $Q$ 行，每行一个指令，指令格式见上文描述，指令中每个参数由空格隔开，保证$(1 \leq p \leq N)$

输出数据

每行一个整数，代表操作 4 和 5 的查询结果

样例输入

5
0 0 0 0 0
1 2
2 5
3 4
4 2
6
1 4 3
4 4
3 1 2 -10
5 2 1
2 2 2 1
5 1 3

样例输出

3
-17
1