European Girls'
Olympiad in Informatics
EGOI - 2022

Tourists

Antalya / Türkiye

English (ISC)

Day1 Tasks

Tourists
Problem Name

Tourists

Input ﬁlestandard input

Output ﬁlestandard output

Time limit

4 seconds

Memory limit

256 megabytes

There are n cities in Utopia, numbered from 1 through n. There are also n − 1 two-way roads
connecting the cities. It is possible to travel between each pair of cities using only these roads.
Because Utopia is very beautiful, there are m tourists, numbered from 1 through m, who are
currently visiting this country. Initially, the i th tourist is visiting city ai . It is possible that multiple
tourists are in the same city; that is, it can be that ai = aj for a pair i, j such that i ≠ j .
Each tourist has an opinion on how interesting their current visit in Utopia is, represented as anumber. Initially each tourist's opinion is 0. In order to encourage further visits, Utopian
government wants to increase the tourists' opinion of the country by organizing events in selectedcities. When an event is held in city c, all tourists who are currently staying there will have theiropinion increased by d, where d is a value depending on the type of the event.
Some of the tourists have planned to travel between cities during their stay in Utopia. Although
traveling from one city to another takes almost no time (thanks to eﬃcient Utopian roads), it still is
an inconvenience and thus results in a lower tourist opinion. To be exact, a tourist who traveled apath consisting of k roads will have their opinion decreased by k (tourists will always choose theshortest path between two cities).
You are asked by the Utopian government to track the tourists' opinions, as they travel through thecountry. As part of this request, you will be given q queries as part of the input. You are supposed
to carry out and answer all queries in the order they appear in the input.

Input
The ﬁrst line contains three integers n, m, q (2 ≤ n ≤ 200 000, 1 ≤ m, q ≤ 200 000) - number ofcities, tourists and queries, respectively.

Tourists (1 of 3)

The second line contains m integers a1 , a2 , ..., am (1 ≤ ai ≤ n), where ai represents the startingcity of the i th tourist.
Next n − 1 lines contain 2 integers each: vi and wi (1 ≤ vi , wi ≤ n, vi ≠ wi ) implying that there
exists a road between city vi and wi .
Next q lines describe queries in the order they are asked. Each line is in one of the following threeforms:
The letter 't' followed by three integers fi , gi , ci (1 ≤ fi ≤ gi ≤ m , 1 ≤ ci ≤ n), meaning that
all tourists with numbers from fi to gi (inclusively) travel to city ci . Those who are already incity ci do not move, and their opinion does not change.
The letter 'e' followed by two integers ci , di (1 ≤ ci ≤ n, 0 ≤ di ≤ 109 ), meaning that in city

ci , an event is being held that increases the tourists' opinion by di .
The letter 'q' followed by one integer vi (1 ≤ vi ≤ m), representing a question about thecurrent opinion of the tourist vi .
It is guaranteed that there is at least one 'q' query in the input.

OutputPrint the answer for all 'q' queries, each in a separate line, in the order they were asked.

Scoring
Subtask 1 (10 points): n, m, q ≤ 200
Subtask 2 (15 points): n, m, q ≤ 2 000
Subtask 3 (25 points): m, q ≤ 2 000
Subtask 4 (25 points): No 'e' queries
Subtask 5 (25 points): No additional constraints

Example Input
8 4 111481
64
63
3765
51
1218

Tourists (2 of 3)

q4t345t227
q4
e 5 10e15
q4t115t221
q1
q2

Example Output
0-1
94-7

Tourists (3 of 3)