T319774 部署（deploy）山东CSP-J2022 入门组3

“万里羽书来未绝，五关烽火昼仍传。” 古时候没有现代信息化战争的技术，只能靠烽火传信和将军运筹帷幄的调兵遣将来取得战争的优势。

为了使消耗最低，现在A国已经在n个城市之间建好了道路和行军部署渠道，使得这n个城市都能互相到达且不存在环（即构成以1 号城市为根节点的树型结构）。每个城市都驻扎了一定数量的兵力。 为了清晰的描述问题，我们给这n个城市进行1到n的编号，且1号城市为树的根节点（数据保证：构成以1号城市为根节点的一棵树）。初始时，第i座城市拥有初始兵力ai。 现在为测试战争部署速度，将军进行了 m 次测试，每次测试可能为以下两种命令的某一种。 【1 x y】（三个数间均用1个空格分开）：向x号城市和以它为根的子树中的所有城市全部增兵y 的数量。 【2 x y】（三个数间均用1个空格分开）：向x号城市和与它直接相连（含父结点和子结点）的城市全部增兵y的数量。 m 条命令发布出去后，将军喊来参谋，进行了q次询问，每次询问第x座城市的最终兵力情况。 该参谋就是小虾米，他又向你求助了，请你帮助他解决问题（q次询问的结果）。

第一行一个正整数n 表示城市数量。 第二行一共n个正整数a1，a2，...an表示每座城市的初始兵力。 接下来n-1行，每行两个整数x，y，表示x和y城市之间有直接相连的道路。 接下来一行一个正整数m，表示m次命令。 接下来m行，每行三个正整数p，x，y表示两种命令其中一种，其中p-1时表示第一种命令，p=2 时表示第二种命令。 接下来一行一个正整数q，表示q次询问。 接下来q行，每行一个正整数x，表示询问编号为x的城市最后的兵力值。

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

对于 100%的数据，数据保证给定的城市和道路能形成树，且 1 号城市为根节点。1