第三题 部署 （deploy）

题目描述

“万里羽书来未绝，五关烽火昼仍传。”

古时候没有现代信息化战争的技术，只能靠烽火传信和将军运筹帷幄的调兵遣将来取得战争的优势。

为了使消耗最低，现在 A 国已经在 n 个城市之间建好了道路和行军部署渠道，使得这 n 个 城市都能互相到达且不存在环（即构成以 1 号城市为根节点的树型结构）。每个城市都驻扎了一定数量的兵力。

为了清晰的描述问题，我们给这 n 个城市进行 1 到 n 的编号，且 1 号城市为树的根节点 （数据保证：构成以 1 号城市为根节点的一棵树）。初始时，第 i 座城市拥有初始兵力 $a_i$。

现在为测试战争部署速度，将军进行了 m 次测试，每次测试可能为以下两种命令的某一种：

• 【1 x y】（三个数间均用 1 个空格分开）：向 x 号城市和以它为根的子树中的所有城市全部增兵 y 的数量。
• 【2 x y】（三个数间均用 1 个空格分开）：向 x 号城市和与它直接相连（含父结点和子结点）的城市全部增兵 y 的数量。

m 条命令发布出去后，将军喊来参谋，进行了 q 次询问，每次询问第 x 座城市的最终兵力情况。 该参谋就是小虾米，他又向你求助了，请你帮助他解决问题（q 次询问的结果）。

输入格式（ 输入文件为 deploy.in）

第一行一个正整数 n 表示城市数量。

第二行一共 n 个正整数 $a_1 , a_2 , . . . ,a_n$ 表示每座城市的初始兵力。

接下来 n-1 行，每行两个整数 x, y ，表示 x 和 y 城市之间有直接相连的道路。

接下来一行一个正整数 m，表示 m 次命令。

接下来 m 行，每行三个正整数 p, x, y 表示两种命令其中一种，其中 p=1 时表示第一种命 令，p=2 时表示第二种命令。

接下来一行一个正整数 q，表示 q 次询问。

接下来 q 行，每行一个正整数 x ，表示询问编号为 x 的城市最后的兵力值。

输出格式（输出文件为 deploy.out）

一共 q 行，每行一个正整数分别对应于每次询问的答案。 输入输出样例

样例一

5
1 2 3 4 5
1 2
1 3
2 4
3 5
4
1 1 2
2 2 3
1 3 3
2 5 1
4
1
2
3
4

6
7
9
9

样例二

4
1 1 1 1
1 2
1 3
1 4
1
1 1 1
2
1
2

2
2

数据范围

$对于 30\% 的数据，1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000,1 ≤ q ≤ 1000；$

$对于 60\% 的数据，1 ≤ n ≤ 10^5 , 1 ≤ m ≤ 10^5 , 1 ≤ q ≤ 10^5 ；$

$其中 10\% 的数据树是一条链， 另外 10\% 的数据只有 1 操作， 另外 10\% 的数据只有 2 操作。$

$ 对于 100\% 的数据，数据保证给定的城市和道路能形成树，且 1 号城市为根节点。1 ≤ n ≤ 10^6, 1 ≤ m ≤ 10^6, 1 ≤ q ≤ 10^6, 1 ≤ a_i ≤ 10^9, 1 ≤ x ≤ n, 1 ≤ y≤ 10，$