Problem Description

You are given a rooted tree with $n$ nodes. Each node has a weight. There are $q$ operations in total, divided into 12 types:

• 0 x y: Set the weights of all nodes in the subtree of $x$ to $y$.
• 1 x: Change the root of the tree to node $x$.
• 2 x y z: Set the weights of all nodes on the simple path from $x$ to $y$ to $z$.
• 3 x: Query the minimum weight in the subtree of $x$.
• 4 x: Query the maximum weight in the subtree of $x$.
• 5 x y: Increase the weights of all nodes in the subtree of $x$ by $y$.
• 6 x y z: Add $z$ to the weights of all nodes on the simple path from $x$ to $y$.
• 7 x y: Query the minimum weight on the simple path from $x$ to $y$.
• 8 x y: Query the maximum weight on the simple path from $x$ to $y$.
• 9 x y: Change the parent of $x$ to $y$. If $y$ is in the subtree of $x$, ignore this operation.
• 10 x y: Query the sum of weights on the simple path from $x$ to $y$.
• 11 x: Query the sum of weights in the subtree of $x$.

Input Format

The first line contains two positive integers $n, q$, representing the number of nodes and the number of operations.
The next $n - 1$ lines each contain two positive integers $u, v$, indicating there is an edge between $u$ and $v$.
Then follow $n$ lines, each containing one integer, representing the node weight.
The next line contains one positive integer, representing the initial root.
Finally, there are $q$ lines, each containing several positive integers, representing one operation.

Output Format

For each operation of type $3, 4, 7, 8, 10, 11$, output one line with one integer, representing the answer.

5 5
2 1
3 1
4 1
5 2
4
1
4
1
2
1
10 2 3
3 1
7 3 4
6 3 3 2
9 5 1

9
1
1

10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5

173
860
103
791
608
1557

Hint

Source: BZOJ 3153

Constraints

For $100\%$ of the data, $1 \le n, q \le 10^5$, and all intermediate computed values are within $[-2^{31}, 2^{31})$.
Since this problem is very hard to implement, you can click here to download the testdata. Submit after passing locally.

Translated by ChatGPT 5