#P11855. [CSP-J2022 山东] 部署

[CSP-J2022 山东] 部署

题目背景

受疫情影响,山东省取消了 CSP-J 2022 认证活动,并于次年三月重新命题,在省内补办比赛。

题目描述

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

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

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

为了清晰的描述问题,我们给这 nn 个城市进行 11nn 的编号,且 11 号城市为树的根节点(数据保证:构成以 11 号城市为根节点的一棵树)。初始时,第 ii 座城市拥有初始兵力 aia_{i}

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

1 x y(三个数间均用 1 个空格分开):向 xx 号城市以它为根的子树中的所有城市全部增兵 yy 的数量。

2 x y(三个数间均用 1 个空格分开):向 xx 号城市与它直接相连(含父结点和子结点)的城市全部增兵 yy 的数量。

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

输入格式

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

第二行一共 nn 个正整数 a1,a2,ana_{1},a_{2},\dots a_{n} 表示每座城市的初始兵力。

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

接下来一行一个正整数 mm,表示 mm 次命令。

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

接下来一行一个正整数 qq,表示 qq 次询问。

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

输出格式

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

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%30\% 的数据,1n1000,1m10001\le n\le1000,1\le m\le1000

对于 60%60\% 的数据,1n105,1m105,1q1051\le n\le10^{5},1\le m\le10^{5},1\le q\le10^{5}

其中 10%10\% 的数据树是一条链,另外 10%10\% 的数据只有 11 操作,另外 10%10\% 的数据只有 22 操作。

对于 100%100\% 的数据,数据保证给定的城市和道路能形成树,且 11 号城市为根节点。$1\le n\le10^{6},1\le m\le10^{6},1\le q\le10^{6},1\le a_{i}\le10^{9},1\le x\le n,1\le y\le10$。