P9320 [EGOI 2022] Tourists / 乌托邦旅行团

Day 1 Problem D. 题面译自 [EGOI2022 tourists](https://stats.egoi.org/media/task_description/2022_tourists_en.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/)

乌托邦有 $n$ 个城市，编号从 $1$ 到 $n$，还有 $n-1$ 条双向公路连接这些城市。只需使用这些道路就可以在每对城市之间旅行。由于乌托邦非常美丽，目前有 $m$ 个游客，编号从 $1$ 到 $m$，正在访问这个国家。最初，第 $i$ 个游客正在访问城市 $a_i$。多个游客可能在同一个城市；也就是说，对于 $i\ne j$，可能有 $a_i=a_j$。 每个游客都有一个关于他们目前在乌托邦的游览有多有趣的评分，用一个数字表示，初始的评分均为 $0$。为了鼓励游客进一步游览，乌托邦政$ $府希望通过在选定的城市组织活动来提高游客的评分。当一个活动在城市 $c$ 举行时，所有目前在那里的游客的评分将增加 $d$，其中 $d$ 是一个取决于活动类型的值。 一些游客计划在乌托邦逗留期间在各城市之间旅行。尽管从一个城市到另一个城市几乎不需要花时间（由于高效的乌托邦道路），但它仍然是一种不便，从而导致游客评分的降低。具体地，一个游客如果走了一条由 $k$ 条道路组成的路径，他们的评分会降低 $k$（游客总是会选择两个城市之间最短的路径）。 乌托邦政$ $府要求你记录下游客们旅行时的评分。作为要求的一部分，你将得到 $q$ 个查询作为输入的一部分。你应该按照输入的顺序回答所有的询问。

第一行三个整数 $n,m,q$——城市数、游客数、询问数。 第二行 $m$ 个整数 $a_1,a_2,\ldots,a_m$，其中 $a_i$ 为第 $i$ 个游客初始所在的城市。 接下来 $n-1$ 行，每行两个整数 $v,w$，表示 $v,w$ 之间有一条双向边。 接下来 $q$ 行，每行描述一个询问。每行的格式是以下三种之一： - 首先一个字母 `t`，接着三个整数 $f_i,g_i,c_i$：所有编号在 $[f_i,g_i]$ 的游客都前往城市 $c_i$。 - 首先一个字母 `e`，接着两个整数 $c_i,d_i$：城市 $c_i$ 举办一个给评分增加 $d$ 的活动。 - 首先一个字母 `q`，接着一个整数 $v_i$：询问现在游客 $v_i$ 的评分。 保证输入中至少有一个操作 `q`。

对于所有操作 `q` 输出一行一个整数。

**数据范围** 对于全部数据，$2\le n\le 2\times 10^5$，$1\le m,q\le 2\times 10^5$，$1\le a_i\le n$，保证输入构成一棵树。操作 `t` 中，$1\le f_i\le g_i\le m$，$1\le c_i\le n$。操作 `e` 中，$1\le c_i\le n$，$0\le d_i\le 10^9$。操作 `q` 中，$1\le v_i\le m$。 - 子任务一（$10$ 分）：$n,m,q\le 200$。 - 子任务二（$15$ 分）：$n,m,q\le 2\times 10^3$。 - 子任务三（$25$ 分）：$m,q\le 2\times 10^3$。 - 子任务四（$25$ 分）：不存在操作 `e`。 - 子任务五（$25$ 分）：无特殊限制。