Problem Description

The country of Katharon has $n$ cities, numbered from $1$ to $n$. To avoid extravagance, there are only $n-1$ roads between the cities, so that you can travel from any city to any other city along the roads.

A spaceship from country X has landed in one of the cities and turned it into its base. X’s usual way to occupy other countries is to build many factories in the base to produce battle robots, and then transport them along the invaded country’s roads to other cities. The commander of country X never backtracks, and believes in unity and absolute fairness. Therefore, when transporting battle robots, he first chooses a destination, then chooses a starting point on the path from the base to that destination, and then distributes the robots evenly to every city on the path from the starting point to the destination. Also, to redistribute robots, the commander will order that, using the same method to choose a start and an end point, the numbers of robots in the cities on that path are reversed. For example, if the robot counts on the chosen path are $1,2,3,4,5$, after reversing they become $5,4,3,2,1$.

On the disk in King Kanari’s hands, the map of Katharon appears. Not only that, it also marks that X’s base is in city $r$, and shows the orders that X’s commander has just issued. “Great!” the king cheers. “If we can learn the enemy’s layout at the first moment, we will surely be able to repel X’s invaders!”

But one problem remains. The disk only shows the orders, but does not show the number of robots in each city, which troubles the king a lot. So he came to you and wants you to design a program to answer his queries. The king only cares about the sum, maximum, and minimum of the robot counts of the cities on the path between two given points, so that he can determine troop deployment, key attack points, and the enemy’s weak spots.

The orders of X’s commander and the queries of King Kanari are as follows:

1. Increase x y w Transport a batch of robots to the cities on the path from $x$ to $y$, and assign $w$ robots to each city.
2. Sum x y Query the sum of robot counts of the cities on the path from $x$ to $y$.
3. Major x y Query the maximum robot count among the cities on the path from $x$ to $y$.
4. Minor x y Query the minimum robot count among the cities on the path from $x$ to $y$.
5. Invert x y Reverse the robot counts of the cities on the path from $x$ to $y$.

For the orders of X’s commander, it is guaranteed that the given $x,y$ satisfy the requirement described above. For King Kanari’s queries, it is not guaranteed that the given $x,y$ satisfy the requirement above.

Input Format

The first line contains three integers $n,m,r$, representing the number of nodes in the tree, the total number of orders and queries, and X’s base.

The next $n-1$ lines each contain two integers $x$ and $y$, representing a road in Katharon.

The next $m$ lines each describe an order or a query, in the format described in the statement.

Output Format

For each query operation, output the required value.

5 8 1
1 2
2 3
3 4
4 5
Sum 2 4
Increase 3 5 3
Minor 1 4
Sum 4 5
Invert 1 3
Major 1 2
Increase 1 5 2
Sum 1 5

0
0
6
3
19

Hint

Constraints: $1\leq n,m\leq 5\times 10^4$, and for transport operations $1\leq w\leq 10^3$.

Translated by ChatGPT 5