题目大意：
给定一棵有根树，每个点有一个权值，提供三种操作：
1.将x节点变为根节点
2.将x到y路径上的点的权值全部改为v
3.询问x的子树中点权的最小值
思路：
用DFS序剖分，记录每个节点入栈出栈的时间，其之间的区间即为子树。操作2用线段树直接搞，而换根先不管，可用原来的DFS序。询问时分类讨论：记最开始的根为root，换根之后，对于当前的根rtnow和询问子树U而言，
①rtnow==U，询问整棵树
②fa[rtnow]==U，询问除了rtnow所在子树以外的整棵树
③rtnow在U的子树里，且距离大于1，询问除了rtnow的除了其祖先是U的儿子的祖先的子树以外的整棵树
④rtnow不在U的子树里，询问U的子树
代码：
#include<cstdio>
#include<iostream>
#define M 2000000
#define INF 2147483647
using namespace std; int cnt,dfn,n,m,a[M],to[M],hson[M],next[M],head[M],id[M],size[M],last[M],pos[M],pa[M],deep[M],top[M],cov[M<<],minv[M<<]; void ins(int x,int y)
{
to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
} void dfs1(int x)
{
size[x]=;
for (int i=head[x];i;i=next[i])
if (to[i]!=pa[x])
{
pa[to[i]]=x,deep[to[i]]=deep[x]+;
dfs1(to[i]),size[x]+=size[to[i]];
if (size[to[i]]>size[hson[x]]) hson[x]=to[i];
}
} void dfs2(int x,int tp)
{
id[x]=++dfn,pos[dfn]=x,top[x]=tp;
if (hson[x]) dfs2(hson[x],tp);
for (int i=head[x];i;i=next[i])
if (to[i]!=pa[x]&&to[i]!=hson[x]) dfs2(to[i],to[i]);
last[x]=dfn;
} void push_down(int k)
{
if (cov[k])
{
cov[k<<]=cov[k<<|]=minv[k<<]=minv[k<<|]=cov[k];
cov[k]=;
}
} void change(int cur,int L,int R,int l,int r,int val)
{
if (L==l && R==r) { cov[cur]=minv[cur]=val; return; }
int mid=L+R>>; push_down(cur);
if (r<=mid) change(cur<<,L,mid,l,r,val);
else if (l>mid) change(cur<<|,mid+,R,l,r,val);
else change(cur<<,L,mid,l,mid,val),change(cur<<|,mid+,R,mid+,r,val);
minv[cur]=min(minv[cur<<],minv[cur<<|]);
} int ask(int cur,int L,int R,int l,int r)
{
if (L==l && R==r) return minv[cur];
int mid=L+R>>; push_down(cur);
if (r<=mid) return ask(cur<<,L,mid,l,r);
if (l>mid) return ask(cur<<|,mid+,R,l,r);
return min(ask(cur<<,L,mid,l,mid),ask(cur<<|,mid+,R,mid+,r));
} void add(int x,int y,int val)
{
for (;top[x]!=top[y];x=pa[top[x]])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
change(,,n,id[top[x]],id[x],val);
}
if (deep[x]>deep[y]) swap(x,y);
change(,,n,id[x],id[y],val);
} int main()
{
scanf("%d%d",&n,&m);
int i,x,y,z,op,rt,root=;
for (i=;i<n;i++) scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for (i=;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&rt);dfs1(rt),dfs2(rt,rt);
for (i=;i<=n;i++) change(,,n,id[i],id[i],a[i]);
while (m--)
{
scanf("%d",&op);
if (op==) scanf("%d",&root);
if (op==) scanf("%d%d%d",&x,&y,&z),add(x,y,z);
if (op==)
{
scanf("%d",&x);
if (x==root) printf("%d\n",ask(,,n,,n));
else if (pa[root]==x) printf("%d\n",min(ask(,,n,,id[root]-),last[root]==n?INF:ask(,,n,last[root]+,n)));
else if (id[root]>=id[x] && id[root]<=last[x])
{
y=root;
while (pa[top[y]]!=x && top[x]!=top[y]) y=pa[top[y]];
if (pa[top[y]]!=x) y=pos[id[x]+];
else y=top[y];
printf("%d\n",min(ask(,,n,,id[y]-),last[y]==n?INF:ask(,,n,last[y]+,n)));
}
else printf("%d\n",ask(,,n,id[x],last[x]));
}
}
return ;
}