题目描述

题目译自 European Girls' Olympiad in Informatics 2022 Day1 T4. Tourists

乌托邦有 $n$ 座城市，编号从 $1$ 到 $n$，之间由 $n-1$ 条双向道路连接。任意两座城市都可以通过这些道路到达。因为乌托邦风景优美，吸引了 $m$ 位游客前来游玩，游客的编号从 $1$ 到 $m$。一开始，第 $i$ 位游客在城市 $a_{i}$。可能会有多位游客同时待在同一座城市，也就是说，对于不同的 $i$ 和 $j$，$a_{i}$ 和 $a_{j}$ 可以相同。

每位游客对当前乌托邦之旅的满意度用一个数字表示，初始时都为 $0$。为了鼓励游客再次造访，乌托邦政府计划在某些城市举办活动来提升他们的满意度。当在城市 $c$ 举办活动时，所有当时在场的游客满意度会增加 $d$，$d$ 的值取决于活动的类型。

有些游客计划在乌托邦逗留期间在城市间旅行。虽然乌托邦的道路效率很高，旅行几乎不费时间，但移动还是会带来不便，导致满意度下降。具体来说，如果一位游客走了一条包含 $k$ 段路的路径（他们总是选择最短路径），满意度会减少 $k$。

乌托邦政府请你帮忙追踪游客的满意度变化，因为他们会在全国各地旅行。作为任务的一部分，输入中会给出 $q$ 个请求，你需要按顺序处理并回答这些请求。

输入格式

第一行包含三个整数 $n, m, q$ $(2 \leq n \leq 200000, 1 \leq m, q \leq 200000)$，分别表示城市数量、游客数量和请求数量。

第二行包含 $m$ 个整数 $a_{1}, a_{2}, \ldots, a_{m}$ $(1 \leq a_{i} \leq n)$，其中 $a_{i}$ 是第 $i$ 位游客的起始城市。

接下来 $n-1$ 行，每行有两个整数 $v_{i}$ 和 $w_{i}$ $(1 \leq v_{i}, w_{i} \leq n, v_{i} \neq w_{i})$，表示城市 $v_{i}$ 和 $w_{i}$ 之间有一条道路。

再接下来 $q$ 行，按顺序描述请求。每行是以下三种形式之一：

• 字母 t 后跟三个整数 $f_{i}, g_{i}, c_{i}$ $(1 \leq f_{i} \leq g_{i} \leq m, 1 \leq c_{i} \leq n)$，表示编号从 $f_{i}$ 到 $g_{i}$ 的所有游客（包含两端）前往城市 $c_{i}$。已经身处 $c_{i}$ 的游客无需移动，他们的满意度保持不变。
• 字母 e 后跟两个整数 $c_{i}, d_{i}$ $(1 \leq c_{i} \leq n, 0 \leq d_{i} \leq 10^{9})$，表示在城市 $c_{i}$ 举办活动，使在场游客的满意度增加 $d_{i}$。
• 字母 q 后跟一个整数 $v_{i}$ $(1 \leq v_{i} \leq m)$，询问当前第 $v_{i}$ 位游客的满意度。

输入中保证至少有一个 q 请求。

输出格式

按请求顺序，针对每个 q 请求输出一个答案，每行一个。

8 4 11
1 4 8 1
6 4
6 3
3 7
6 5
5 1
1 2
1 8
q 4
t 3 4 5
t 2 2 7
q 4
e 5 10
e 1 5
q 4
t 1 1 5
t 2 2 1
q 1
q 2

0
-1
9
4
-7

数据范围与提示

详细子任务附加限制及分值如下表所示。