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,