{"raw_statement":[{"iden":"background","content":"Day 1 Problem D.\n\n题面译自 [EGOI2022 tourists](https://stats.egoi.org/media/task_description/2022_tourists_en.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)"},{"iden":"statement","content":"乌托邦有 $n$ 个城市，编号从 $1$ 到 $n$，还有 $n-1$ 条双向公路连接这些城市。只需使用这些道路就可以在每对城市之间旅行。由于乌托邦非常美丽，目前有 $m$ 个游客，编号从 $1$ 到 $m$，正在访问这个国家。最初，第 $i$ 个游客正在访问城市 $a_i$。多个游客可能在同一个城市；也就是说，对于 $i\\ne j$，可能有 $a_i=a_j$。\n\n每个游客都有一个关于他们目前在乌托邦的游览有多有趣的评分，用一个数字表示，初始的评分均为 $0$。为了鼓励游客进一步游览，乌托邦政$ $府希望通过在选定的城市组织活动来提高游客的评分。当一个活动在城市 $c$ 举行时，所有目前在那里的游客的评分将增加 $d$，其中 $d$ 是一个取决于活动类型的值。\n\n一些游客计划在乌托邦逗留期间在各城市之间旅行。尽管从一个城市到另一个城市几乎不需要花时间（由于高效的乌托邦道路），但它仍然是一种不便，从而导致游客评分的降低。具体地，一个游客如果走了一条由 $k$ 条道路组成的路径，他们的评分会降低 $k$（游客总是会选择两个城市之间最短的路径）。\n\n乌托邦政$ $府要求你记录下游客们旅行时的评分。作为要求的一部分，你将得到 $q$ 个查询作为输入的一部分。你应该按照输入的顺序回答所有的询问。"},{"iden":"input","content":"第一行三个整数 $n,m,q$——城市数、游客数、询问数。\n\n第二行 $m$ 个整数 $a_1,a_2,\\ldots,a_m$，其中 $a_i$ 为第 $i$ 个游客初始所在的城市。\n\n接下来 $n-1$ 行，每行两个整数 $v,w$，表示 $v,w$ 之间有一条双向边。\n\n接下来 $q$ 行，每行描述一个询问。每行的格式是以下三种之一：\n\n- 首先一个字母 `t`，接着三个整数 $f_i,g_i,c_i$：所有编号在 $[f_i,g_i]$ 的游客都前往城市 $c_i$。\n- 首先一个字母 `e`，接着两个整数 $c_i,d_i$：城市 $c_i$ 举办一个给评分增加 $d$ 的活动。\n- 首先一个字母 `q`，接着一个整数 $v_i$：询问现在游客 $v_i$ 的评分。\n\n保证输入中至少有一个操作 `q`。"},{"iden":"output","content":"对于所有操作 `q` 输出一行一个整数。"},{"iden":"note","content":"**数据范围**\n\n对于全部数据，$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$。\n\n- 子任务一（$10$ 分）：$n,m,q\\le 200$。\n- 子任务二（$15$ 分）：$n,m,q\\le 2\\times 10^3$。\n- 子任务三（$25$ 分）：$m,q\\le 2\\times 10^3$。\n- 子任务四（$25$ 分）：不存在操作 `e`。\n- 子任务五（$25$ 分）：无特殊限制。"}],"translated_statement":null,"sample_group":[["8 4 11\n1 4 8 1\n6 4\n6 3\n3 7\n6 5\n5 1\n1 2\n1 8\nq 4\nt 3 4 5\nt 2 2 7\nq 4\ne 5 10\ne 1 5\nq 4\nt 1 1 5\nt 2 2 1\nq 1\nq 2","0\n-1\n9\n4\n-7"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}