Tree and Queries 13

A rooted tree with $N$ vertices is given. The vertices are numbered from 1 to $N$. The weight of vertex $i$ is $A_i$. Initially, vertex $r$ is the root.

Write a program that processes the following queries.

• 0 x y: Change the weights of all vertices in the subtree of $x$ to $y$.
• 1 r: Change the root of the tree to $r$.
• 2 x y z: Change the weights of all vertices on the path between $x$ and $y$ to $z$.
• 3 x: Print the minimum weight among the vertices in the subtree of $x$.
• 4 x: Print the maximum weight among the vertices in the subtree of $x$.
• 5 x y: Add $y$ to the weights of all vertices in the subtree of $x$.
• 6 x y z: Add $z$ to the weights of all vertices on the path between $x$ and $y$.
• 7 x y: Print the minimum weight among the vertices on the path between $x$ and $y$.
• 8 x y: Print the maximum weight among the vertices on the path between $x$ and $y$.
• 9 x y: Change the parent of $x$ to $y$. If vertex $y$ is in the subtree of $x$, ignore this query.
• 10 x y: Print the sum of the weights of the vertices on the path between $x$ and $y$.
• 11 x: Print the sum of the weights of the vertices in the subtree of $x$.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 10^5$).

Each of the next $N-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le N$), the endpoints of an edge.

Each of the next $N$ lines contains the weight $A_i$ of vertex $i$.

The next line contains the initial root $r$ ($1 \le r \le N$).

The next $M$ lines contain the queries described above.

All integers in the input fit in the C++ int type. The input is given so that the sum of the weights of all vertices never exceeds the int range while the queries are processed.

For each query, print its result on its own line, in the order the queries are given.