SP19154 INS14M - Terrorist Attack

在迪戈的最后一次面试中，他接到了一项任务：给出一张城市地图，这张地图描绘了城市中的 $N$ 个交叉口，它们通过长度为 $1$ 的道路连接。任意两个交叉口之间仅有一条唯一的路径。每个交叉口都有一个从 $1$ 到 $N$ 的独特编号。城市中有 $M$ 位市民，每天这些市民会访问一些特定的交叉口。 有些交叉口上设置了军营。恐怖分子正策划通过袭击部分交叉口来攻击这座城市，但由于军营的存在，他们在每个交叉口所能引发的爆炸强度是有限的。放置在一个交叉口的炸弹强度定义为：从任何一个军营到该目标交叉口的最小距离。所有经过被袭击交叉口的市民，他们受到的伤害将增加该交叉口上的炸弹强度。军营的分布和恐怖分子的目标是通过如下查询形式给出的： - `1 J`：在交叉口 $J$ 建立一个新的军营。 - `2 J`：恐怖分子袭击了交叉口 $J$。 - `3 J`：输出到目前为止，所有访问过交叉口 $J$ 的市民所受到的总伤害值。 初始情况下，在交叉口 $1$ 上建有一个军营。所有市民的初始伤害值已经给定。

第一行包含三个整数 $N, M, Q$，分别代表交叉口数量、市民数量和后续的查询数量。 接下来有 $N-1$ 行，每行两个整数 $U$ 和 $V$，表示有一条连接交叉口 $U$ 和 $V$ 的道路。 接下来 $M$ 行，每行一个整数，表示第 $i$ 个市民的初始伤害值 $a[i]$。再接下来的 $M$ 行描述每个市民访问的交叉口（每行的第一个整数 $X$ 表示第 $i$ 位市民访问的交叉口数量，后续是 $X$ 个整数表示具体交叉口）。 接下来 $Q$ 行给出相应的查询。每个查询由两个整数 $T, J$ 构成，其中 $T$ 为查询类型（可以是 $1$、$2$ 或 $3$），$J$ 为查询的目标交叉口编号。

对于所有类型为 `3` 的查询，输出一个整数，表示查询结果。

$$1 \leq N, M, Q \leq 10^5$$ **本翻译由 AI 自动生成**