一道换根树剖好题，思维很巧妙。
去食堂时开玩笑跟机房数据结构之神说树剖可以换根，他一本正经的说：“树剖真的可以换根。”然后当晚考试就考了这道题。（一口毒奶）
本题要求:换根+链修改+子树min
换根和链修改首先可以想到LCT，然而LCT弱于维护子树，这种维护子树最值更是麻烦。
考虑树剖。换根肯定不能重构树剖。那就转化一下？
画个图看看：
换完后长这样：
（x为原树根，y为要换的根）
抽象点理解，就是把y拎了起来（可以在脑中yy一个GIF）
注意到，点1和点x子树变了，其他的都没变。这两个点都是y的祖先，也就是说原树中为y的祖先的点子树变了
抽象来说，对于某个点，y本来在它下面。现在要把在它下面的点y拎到上面去变成根，那么本来在它上面的点就要坠下去变成它的子树，而本来在它下面的点就要跑到上面去，从它的子树中分开。（可能很绕口。。。）
那它的子树变成啥了？在原树中从y向上跳，一直到它的某一个儿子，那么整棵树-这个儿子的子树=它的新子树
为什么呢？假设y向上跳到的它的儿子为z，z的子树都会跑到它的上面，而它上面的点成了它的新子树，再加上它原子树中剩下的点就是新子树
（z的子树+它原子树中不是z的子树的点+它上面的点【不是它子树中的点】=整棵树，它原子树中不是z的子树的点+它上面的点=新子树->整棵树-z的子树=它的新子树）
然后就是怎么跳了。当然可以用倍增LCA。不过树剖写都写了，怎么能不好好用用树剖呢？考虑直接跳重链（假设从x跳到y的儿子z）：
1.如果z是y的重儿子，一定会有某一时刻top[x]==top[y]（因为它们在同一条重链上），那就返回y的重儿子
2.如果z是y的轻儿子，一定会有某一时刻top[x]的父亲是y，那就返回top[x]（可以画个图理解）
这样就可以不改变树的结构换根了QwQ
最后说一下细节：
1.数据范围是小于等于$2^{31}$，等于的话会爆int啊，也不要像我一样inf只开到0x3f3f3f3f，WA调了一小时。。。
2.可以用LCA来判断是否是当前树根的祖先。而且树剖都写了，正好用树剖求LCA，省空间省时间省码量（而且据说树剖LCA比倍增常数小）
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 100005
#define inf 0x3f3f3f3f
const long long INF = 1e11;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<class T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar()；}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}//快读
int head[maxn],num;
struct edge{
int pre,to;
}e[maxn<<1];
inline void add(int from,int to){
e[++num].pre=head[from],head[from]=num,e[num].to=to;
}//邻接表
long long a[maxn];
int seg[maxn],top[maxn],pos[maxn],deep[maxn],fa[maxn],son[maxn],siz[maxn],cap;
//seg就是树剖第二次dfs打的标记，cap是当前首都
struct Segment_Tree{
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
long long dat[maxn<<2];
int tag[maxn<<2];
inline void update(int node){
dat[node]=min(dat[ls(node)],dat[rs(node)]);
}
inline void pushdown(int node){
dat[ls(node)]=dat[rs(node)]=dat[node];
tag[ls(node)]=tag[rs(node)]=1;
tag[node]=0;
}
void build(int l,int r,int node){
if(l==r){
dat[node]=a[pos[l]];
return;
}
int mid=l+r>>1;
build(l,mid,ls(node));
build(mid+1,r,rs(node));
update(node);
}
void change(int L,int R,int l,int r,int node,long long d){
if(L<=l&&R>=r){
dat[node]=d,tag[node]=1;
return;
}
if(tag[node])pushdown(node);
int mid=l+r>>1;
if(L<=mid)change(L,R,l,mid,ls(node),d);
if(R>mid)change(L,R,mid+1,r,rs(node),d);
update(node);
}
long long ask(int L,int R,int l,int r,int node){
if(L<=l&&R>=r)return dat[node];
if(tag[node])pushdown(node);
int mid=l+r>>1;
long long ans=INF;
if(L<=mid)ans=ask(L,R,l,mid,ls(node));
if(R>mid)ans=min(ans,ask(L,R,mid+1,r,rs(node)));
return ans;
}
};//线段树
struct Tree_Chain_Spilt{
//问一句，有谁知道树剖真正的英文名是啥吗。。。我强迫症受不了啊。。。
Segment_Tree st;
void dfs1(int node){
siz[node]=1;
for(register int i=head[node];i;i=e[i].pre){
if(!siz[e[i].to]){
fa[e[i].to]=node;
deep[e[i].to]=deep[node]+1;
dfs1(e[i].to);
if(siz[e[i].to]>siz[son[node]])son[node]=e[i].to;
siz[node]+=siz[e[i].to];
}
}
}
void dfs2(int node){
seg[node]=++seg[0];
pos[seg[0]]=node;
if(son[node]){
top[son[node]]=top[node];
dfs2(son[node]);
for(register int i=head[node];i;i=e[i].pre)
if(!seg[e[i].to]){
top[e[i].to]=e[i].to;
dfs2(e[i].to);
}
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}
return deep[x]<deep[y]?x:y;
}//树剖求LCA
void change(int x,int y,int d){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
st.change(seg[top[x]],seg[x],1,seg[0],1,d);
x=fa[top[x]];
}
if(deep[x]<deep[y])swap(x,y);
st.change(seg[y],seg[x],1,seg[0],1,d);
}
int Get(int x,int y){
while(top[x]!=top[y]&&fa[top[y]]!=x)y=fa[top[y]];
if(fa[top[y]]==x)return top[y];
return son[x];
}//向上跳的函数
long long ask(int x){
if(x==cap)return st.dat[1];//注意特判查询首都
else if(lca(cap,x)==x){//用LCA判断x是否是cap的祖先
int k=Get(x,cap);
long long ans=INF;
if(seg[k]>1)ans=st.ask(1,seg[k]-1,1,seg[0],1);
if(seg[k]+siz[k]<=seg[0])ans=min(ans,st.ask(seg[k]+siz[k],seg[0],1,seg[0],1));
//注意判一下seg的边界，不过好像不判也行。。
return ans;
}
else return st.ask(seg[x],seg[x]+siz[x]-1,1,seg[0],1);
}
}tcs;
int main(){
int n=read(),m=read();
for(register int i=1;i<n;++i){
int x=read(),y=read();
add(x,y),add(y,x);
}
for(register int i=1;i<=n;++i)
a[i]=read<long long>();
cap=read();
tcs.dfs1(cap);
tcs.dfs2(cap);
tcs.st.build(1,seg[0],1);
while(m--){
int s=read();
if(s==1)cap=read();
else if(s==2){
int x=read(),y=read();
long long d=read<long long>();
tcs.change(x,y,d);
}
else {
int x=read();
printf("%lld\n",tcs.ask(x));
}
}
return 0;
}
