[CSP-J 2022 山东] 部署(Troop Deployment)

题目描述

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

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

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

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

为了清晰的描述问题，我们给这 $n$ 个城市进行 $1$ 到 $n$ 的编号，且 $1$ 号城市为树的根节点（数据保证：构成以 $1$ 号城市为根节点的一棵树）。初始时，第 $i$ 座城市拥有初始兵力 $a_{i}$。

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

1 x y（三个数间均用 1 个空格分开）：向 $x$ 号城市和以它为根的子树中的所有城市全部增兵 $y$ 的数量。

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

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

输入格式

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

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

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

接下来一行一个正整数 $m$，表示 $m$ 次命令。

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

接下来一行一个正整数 $q$，表示 $q$ 次询问。

接下来 $q$ 行，每行一个正整数 $x$ ，表示询问编号为 $x$ 的城市最后的兵力值。

输出格式

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

样例输入 #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

样例输出 #1

6
7
9
9

样例输入 #2

4
1 1 1 1
1 2
1 3
1 4
1
1 1 1
2
1
2

样例输出 #2

2
2

数据范围

数据范围

对于 $30\%$ 的数据，$1\le n\le1000,1\le m\le1000$；

对于 $60\%$ 的数据，$1\le n\le10^{5},1\le m\le10^{5},1\le q\le10^{5}$；

其中 $10\%$ 的数据树是一条链，另外 $10\%$ 的数据只有 $1$ 操作，另外 $10\%$ 的数据只有 $2$ 操作。

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

2025-06-26 增加 Hack 一组

知识点与难度

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1400。

测试点分布

出处：原题链接