You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

zcwwzdjn 在追杀 zhx ，而 zhx 逃入了一个遥远的国度。当 zcwwzdjn 准备进入遥远的国度继续追杀时，守护神 RapiD 阻拦了 zcwwzdjn 的去路，他需要 zcwwzdjn 完成任务后才能进入遥远的国度继续追杀。

问题是这样的：遥远的国度有 $n$ 个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，第 $i$ 个的防御值为 $val_i$，有些时候 RapiD 会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。

RapiD 想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。

由于 RapiD 无法解决这个问题，所以他拦住了 zcwwzdjn 希望他能帮忙。但 zcwwzdjn 还要追杀 zhx，所以这个重大的问题就被转交到了你的手上。

输入格式

第 $1$ 行两个整数 $n\ m$，代表城市个数和操作数。

第 $2$ 行至第 $n$ 行，每行两个整数 $u\ v$，代表城市 $u$ 和城市 $v$ 之间有一条路。

第 $n+1$ 行，有 $n$ 个整数，第 $i$ 个代表第 $i$ 个点的初始防御值 $val_i$。

第 $n+2$ 行一个整数 $id$，代表初始的首都为 $id$。

第 $n+3$ 行至第 $n+m+2$ 行，首先有一个整数 $opt$。

如果 $opt=1$，接下来有一个整数 $id$，代表把首都修改为 $id$；

如果 $opt=2$，接下来有三个整数 $x\ y\ v$，代表将 $x\ y$ 路径上的所有城市的防御值修改为 $v$；

如果 $opt=3$，接下来有一个整数 $id$，代表询问以城市 $id$ 为根的子树中的最小防御值。

输出格式

对于每个 $opt=3$ 的操作，输出一行代表对应子树的最小点权值。

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

提示

对于 $20\%$ 的数据，$n\le 1000,m\le 1000$。

对于另外 $10\%$ 的数据，$n\le 100000,m\le 100000$，保证修改为单点修改。

对于另外 $10\%$ 的数据，$n\le100000,m \le 100000$，保证树为一条链。

对于另外 $10\%$ 的数据，$n\le 100000,m\le100000$，没有修改首都的操作。

对于 $100\%$ 的数据，$1 \leq n\le 100000,1 \leq m \le 100000,0<val_i<2^{31}$。