U285018 部署
题目背景
CSP-J2022山东补赛第三题
题目描述
“万里羽书来未绝,五关烽火昼仍传。” 古时候没有现代信息化战争的技术,只能靠烽火传信和将军运筹帷幄的调兵遣将来取得战
争的优势。
为了使消耗最低,现在 A 国已经在 n 个城市之间建好了道路和行军部署渠道,使得这 n 个
城市都能互相到达且不存在环(即构成以 1 号城市为根节点的树型结构)。每个城市都驻扎了
一定数量的兵力。
为了清晰的描述问题,我们给这 n 个城市进行 1 到 n 的编号,且 1 号城市为树的根节点
(数据保证:构成以 1 号城市为根节点的一棵树)。初始时,第 i 座城市拥有初始兵力 a。
现在为测试战争部署速度,将军进行了 m 次测试,每次测试可能为以下两种命令的某一
种:
【1 x y】(三个数间均用 1 个空格分开):向 x 号城市和以它为根的子树中的所有城市全部增
兵 y 的数量。
【2 x y】(三个数间均用 1 个空格分开):向 x 号城市和与它直接相连(含父结点和子结点)
的城市全部增兵 y 的数量。
m 条命令发布出去后,将军喊来参谋,进行了 q 次询问,每次询问第 x 座城市的最终兵力
情况。
该参谋就是小虾米,他又向你求助了,请你帮助他解决问题(q 次询问的结果)。
输入格式
无
输出格式
无
说明/提示
数据范围:
对于 30% 的数据,1 ≤ n ≤ 1000,1 ≤ m ≤ 1000,1 ≤ q ≤ 1000;
对于 60% 的数据,1 ≤ n ≤ 100000
, 1 ≤ m ≤ 100000
, 1 ≤ q ≤ 100000
;
其中 10% 的数据树是一条链, 另外 10% 的数据只有 1 操作, 另外 10% 的数据只有 2 操作。
对于 100% 的数据,数据保证给定的城市和道路能形成树,且 1 号城市为根节点。1 ≤ n ≤1000000
, 1 ≤ m ≤ 1000000
, 1 ≤ a ≤ 1000000000
, 1 ≤ x ≤ n, 1 ≤ y ≤ 10,