P5649 Sone1

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$.

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.

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

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](https://darkbzoj.cc/data/3153.zip) to download the testdata. Submit after passing locally. Translated by ChatGPT 5