#P11855. [CSP-J2022 山东] 部署
[CSP-J2022 山东] 部署
题目背景
受疫情影响,山东省取消了 CSP-J 2022 认证活动,并于次年三月重新命题,在省内补办比赛。
题目描述
“万里羽书来未绝,五关烽火昼仍传。”
古时候没有现代信息化战争的技术,只能靠烽火传信和将军运筹帷幄的调兵遣将来取得战争的优势。
为了使消耗最低,现在 A 国已经在 个城市之间建好了道路和行军部署渠道,使得这 个城市都能互相到达且不存在环(即构成以 号城市为根节点的树型结构)。每个城市都驻扎了一定数量的兵力。
为了清晰的描述问题,我们给这 个城市进行 到 的编号,且 号城市为树的根节点(数据保证:构成以 号城市为根节点的一棵树)。初始时,第 座城市拥有初始兵力 。
现在为测试战争部署速度,将军进行了 次测试,每次测试可能为以下两种命令的某一种:
1 x y
(三个数间均用 1 个空格分开):向 号城市和以它为根的子树中的所有城市全部增兵 的数量。
2 x y
(三个数间均用 1 个空格分开):向 号城市和与它直接相连(含父结点和子结点)的城市全部增兵 的数量。
条命令发布出去后,将军喊来参谋,进行了 次询问,每次询问第 座城市的最终兵力情况。 该参谋就是小虾米,他又向你求助了,请你帮助他解决问题( 次询问的结果)。
输入格式
第一行一个正整数 表示城市数量。
第二行一共 个正整数 表示每座城市的初始兵力。
接下来 行,每行两个整数 ,表示 和 城市之间有直接相连的道路。
接下来一行一个正整数 ,表示 次命令。
接下来 行,每行三个正整数 表示两种命令其中一种,其中 时表示第一种命令, 时表示第二种命令。
接下来一行一个正整数 ,表示 次询问。
接下来 行,每行一个正整数 ,表示询问编号为 的城市最后的兵力值。
输出格式
一共 行,每行一个正整数分别对应于每次询问的答案。
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
提示
数据范围
对于 的数据,;
对于 的数据,;
其中 的数据树是一条链,另外 的数据只有 操作,另外 的数据只有 操作。
对于 的数据,数据保证给定的城市和道路能形成树,且 号城市为根节点。$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$。