Background

Day 1 Problem D.

Translated from EGOI2022 tourists.

Problem Description

Utopia has $n$ cities, numbered from $1$ to $n$, and $n-1$ bidirectional roads connecting these cities. Using only these roads, it is possible to travel between every pair of cities. Since Utopia is very beautiful, there are currently $m$ tourists, numbered from $1$ to $m$, visiting the country. Initially, tourist $i$ is visiting city $a_i$. Multiple tourists may be in the same city; that is, for $i\ne j$, it is possible that $a_i=a_j$.

Each tourist has a rating for how interesting their current trip in Utopia is, represented by a number, and all initial ratings are $0$. To encourage tourists to explore more, the Utopian government hopes to increase tourists' ratings by organizing events in selected cities. When an event is held in city $c$, the ratings of all tourists currently there increase by $d$, where $d$ depends on the type of event.

Some tourists plan to travel between cities during their stay in Utopia. Although traveling from one city to another takes almost no time (thanks to the efficient Utopian roads), it is still an inconvenience and thus decreases the tourists' ratings. Specifically, if a tourist travels along a path consisting of $k$ roads, their rating decreases by $k$ (tourists always choose the shortest path between two cities).

The Utopian government asks you to record the tourists' ratings as they travel. As part of this requirement, you are given $q$ queries as input. You should answer all queries in the order they appear in the input.

Input Format

The first line contains three integers $n,m,q$ — the number of cities, the number of tourists, and the number of queries.

The second line contains $m$ integers $a_1,a_2,\ldots,a_m$, where $a_i$ is the initial city of tourist $i$.

The next $n-1$ lines each contain two integers $v,w$, indicating that there is a bidirectional edge between $v$ and $w$.

The next $q$ lines each describe a query. Each line has one of the following three formats:

• First a letter t, followed by three integers $f_i,g_i,c_i$: all tourists with indices in $[f_i,g_i]$ travel to city $c_i$.
• First a letter e, followed by two integers $c_i,d_i$: city $c_i$ holds an event that increases ratings by $d$.
• First a letter q, followed by one integer $v_i$: ask for the current rating of tourist $v_i$.

It is guaranteed that there is at least one operation q in the input.

Output Format

For each operation q, output one integer per line.

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

Hint

Constraints

For all testdata, $2\le n\le 2\times 10^5$, $1\le m,q\le 2\times 10^5$, $1\le a_i\le n$. The input is guaranteed to form a tree. In operation t, $1\le f_i\le g_i\le m$, $1\le c_i\le n$. In operation e, $1\le c_i\le n$, $0\le d_i\le 10^9$. In operation q, $1\le v_i\le m$.

• Subtask 1 ($10$ points): $n,m,q\le 200$.
• Subtask 2 ($15$ points): $n,m,q\le 2\times 10^3$.
• Subtask 3 ($25$ points): $m,q\le 2\times 10^3$.
• Subtask 4 ($25$ points): there are no operations e.
• Subtask 5 ($25$ points): no additional constraints.

Translated by ChatGPT 5