记录编号	284279	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	遥远的国度	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	3.033 s
提交时间	2016-07-17 16:42:48	内存使用	15.05 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10 ;
const int inf = ~0U>>1;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');
	if( ch == '-' ) flag = true,ch=getchar();
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
	if( flag ) x=-x;
}
inline int cat_min(const int &a,const int &b){
	return a<b ? a:b;
}
inline int cat_max(const int &a,const int &b){
	return a>b ? a:b;
}
struct Edge{
	int to,next;
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v){
	G[++cnt].to = v;
	G[cnt].next = head[u];
	head[u] = cnt;
}
int n,m,root;
int T[maxn<<2],cov[maxn<<2];
int a[maxn],left[maxn],right[maxn],son[maxn];
int deep[maxn],pos[maxn],fa[maxn][20],size[maxn],top[maxn],tim;
#define v G[i].to
inline void dfs1(int x){
	size[x]=1;son[x]=0;
	for(int i = head[x];i;i = G[i].next){
		if(v != fa[x][0]) {
			fa[v][0] = x;
			deep[v] = deep[x] + 1; 
			dfs1(v);
			size[x] += size[v];
			if(size[v] > size[son[x]]) son[x] = v;
		}
	}
}
inline void dfs2(int x,int tp){
	left[x] = ++tim;
	top[x] = tp;
	pos[tim] = x;
	if(son[x]) dfs2(son[x],tp);
	for(int i = head[x];i;i = G[i].next) 
		if(v != fa[x][0] && v != son[x]) dfs2(v,v);
	right[x] = tim; 
}
#undef v
inline void build(int rt,int l,int r){
	cov[rt] = -1;
	if(l == r){
		T[rt] = a[pos[l]];
		cov[rt] = -1;
		return;
	}
	int mid = l+r >> 1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	T[rt] = cat_min(T[rt<<1],T[rt<<1|1]);
}
inline void pushdown(int rt){
	if(cov[rt] != -1){
		T[rt<<1] = T[rt<<1|1] = cov[rt<<1] = cov[rt<<1|1] = cov[rt];
		cov[rt] = -1;
	}
}
int Qx,Qy,ans;
inline void change(int rt,int l,int r,int v){
	if(Qx <= l && r <= Qy){ 
		T[rt] = v;
		cov[rt] = v;
		return;
	}
	pushdown(rt);
	int mid = l+r >> 1;
	if(Qx <= mid) change(rt<<1,l,mid,v);
	if(Qy >  mid) change(rt<<1|1,mid+1,r,v);
	T[rt] = cat_min(T[rt<<1],T[rt<<1|1]);
}
inline void query(int rt,int l,int r){
	if(Qx > Qy){
		ans = inf;
		return;
	}
	if(Qx <= l && r <= Qy){
		ans = cat_min(ans,T[rt]);
		return ;
	}
	pushdown(rt);
	int mid = l+r >> 1;
	if(Qx <= mid) query(rt<<1,l  ,mid);
	if(Qy >  mid) query(rt<<1|1,mid+1,r);
	T[rt] = cat_min(T[rt<<1],T[rt<<1|1]);
}
inline int query(int x,int y) {ans = inf;Qx = x;Qy = y;query(1,1,n); return ans;}
inline void change(int x,int y,int v) {Qx = x; Qy = y; change(1,1,n,v);}
inline void init(){
	for(int j = 1;j <= 19;++ j)
		for(int i = 1;i <= n;++ i)
			fa[i][j] = fa[fa[i][j-1]][j-1];
}
inline void fix(int x,int y,int v){
	int fx = top[x],fy = top[y];
	while(fx != fy) {
		if(deep[fx] < deep[fy]) {swap(x,y); swap(fx,fy);}
		change(left[fx],left[x],v);
		x = fa[fx][0]; fx = top[x];
	} 
	if(deep[x] > deep[y]) swap(x,y);
	change(left[x],left[y],v);
}
int main(){
	freopen("bbbbb.in","r",stdin);
	freopen("bbbbb.out","w",stdout);
	read(n);read(m);
	int u,v,w;
	for(int i = 1;i < n;++ i){
		read(u);read(v);
		add(u,v); add(v,u);
	}
	for(int i = 1;i <= n;++i) read(a[i]);
	read(root);
	dfs1(root);
	dfs2(root,root); 
	init();
	build(1,1,n);
	int op;
	while(m --){
		read(op); 
		if(op == 1) read(u),root = u;
		else{
			if(op == 2){
				read(u); read(v); read(w); 
				fix(u,v,w);
			}else{
				read(u);
				if(root == u) printf("%d\n",query(1,n));
				else{
					if(left[u] <= left[root] && right[root] <= right[u]){
						int y = root,d = deep[y] - deep[u] - 1;
						for(int i = 0;i <= 19;++i) 
							if(d & (1 << i)) y=fa[y][i];
						printf("%d\n",cat_min(query(1,left[y]-1),query(right[y]+1,n)));
					}else printf("%d\n",query(left[u],right[u]));
				}
			}
		}   
	}
	return 0;
}