P3313 [SDOI2014] Travel

Country S has $N$ cities, numbered from $1$ to $N$. The cities are connected by $N-1$ undirected roads, forming a structure where starting from any city, one can reach all other cities. Each city believes in a different religion; common beliefs include the Church of the Flying Spaghetti Monster, the Invisible Pink Unicorn, and Jediism. For convenience, we use different positive integers to represent various religions. Residents of Country S often travel. They always take the shortest path, and to avoid trouble, they only stay overnight in cities whose religion is the same as theirs. Of course, the destination of the trip also has the same religion as the traveler. Country S assigns a distinct travel rating to each city. Travelers often record the sum or the maximum of the ratings of the cities where they stayed overnight along the way, including the start and end cities. In the history of Country S, the following types of events often occur: - `CC x c`: All residents of city $x$ convert to religion $c$. - `CW x w`: The rating of city $x$ is adjusted to $w$. - `QS x y`: A traveler starts from city $x$, goes to city $y$, and records the sum of the ratings of the cities where they stayed overnight along the way. - `QM x y`: A traveler starts from city $x$, goes to city $y$, and records the maximum of the ratings of the cities where they stayed overnight along the way. The recorded numbers have been lost, but the religion and rating of each city before the records began, as well as the event log itself, are intact. Based on this information, restore the numbers that the travelers recorded. For convenience, we assume that the interval between events is long enough so that during any single trip, all cities’ ratings and religions remain unchanged.

The first line contains the integers $N, Q$, representing the number of cities and the number of events, respectively. The next $N$ lines: on the $(i+1)$-th line, two integers $W_i, C_i$ denote the initial rating and religion of city $i$ before the records began. The next $N-1$ lines each contain two integers $x, y$, indicating an undirected road between cities $x$ and $y$. The next $Q$ lines each contain one operation, in one of the formats described above.

For each `QS` and `QM` event, output one line containing the number recorded by the traveler.

For $100\%$ of the testdata, $N, Q \le 10^5$, $C \le 10^5$. It is guaranteed that for all `QS` and `QM` events, the start and end cities have the same religion. At any time, a city’s rating is a positive integer not exceeding $10^4$, and the religion value does not exceed $C$. Translated by ChatGPT 5