题目背景

Day 1 Problem D.

题面译自 EGOI2022 tourists。

题目描述

乌托邦有 $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 输出一行一个整数。

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

提示

数据范围

对于全部数据，$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$ 分）：无特殊限制。