Description

zcwwzdjn is hunting down zhx, and zhx has fled to a distant kingdom. When zcwwzdjn is about to enter the distant kingdom to continue the pursuit, the guardian RapiD blocks his way. He must complete a task before he can enter the distant kingdom and continue the chase.

Here is the problem: the distant kingdom has $n$ cities. These cities are connected by some roads and they form a tree. The kingdom has a capital, and we can regard this capital as the root of the whole tree; however, the capital may change to another city at any time. Each city has a defense value; the $i$-th city's defense value is $val_i$. Sometimes RapiD will set the defense values of all cities on the path between two cities to a certain value.

RapiD wants to know, at some moment, if we regard the capital as the root of the whole tree, then what is the minimum defense value among all cities in the subtree rooted at some city.

Since RapiD cannot solve this, he stopped zcwwzdjn hoping he could help. But zcwwzdjn still needs to hunt down zhx, so this important problem has been handed over to you.

Input Format

Line $1$: two integers $n\ m$, representing the number of cities and the number of operations.

Lines $2$ to $n$: each line contains two integers $u\ v$, meaning there is a road between city $u$ and city $v$.

Line $n+1$: $n$ integers; the $i$-th integer is the initial defense value $val_i$ of the $i$-th city.

Line $n+2$: one integer $id$, meaning the initial capital is $id$.

Lines $n+3$ to $n+m+2$: first there is an integer $opt$.

• If $opt=1$, then there is an integer $id$, meaning the capital is updated to $id$.
• If $opt=2$, then there are three integers $x\ y\ v$, meaning the defense values of all cities on the path $x\ y$ are set to $v$.
• If $opt=3$, then there is an integer $id$, meaning you need to query the minimum defense value in the subtree rooted at city $id$ (with the current capital regarded as the root of the whole tree).

Output Format

For each $opt=3$ operation, output one line containing the minimum defense value in the corresponding subtree.

3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1

1
2
3
4

Hint

For $20\%$ of the testdata, $n\le 1000,m\le 1000$.

For another $10\%$ of the testdata, $n\le 100000,m\le 100000$, and updates are guaranteed to be point updates.

For another $10\%$ of the testdata, $n\le100000,m \le 100000$, and the tree is guaranteed to be a chain.

For another $10\%$ of the testdata, $n\le 100000,m\le100000$, and there are no operations that change the capital.

For $100\%$ of the testdata, $1 \leq n\le 100000,1 \leq m \le 100000,0<val_i<2^{31}$.

Translated by ChatGPT 5