记录编号	313715	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	遥远的国度	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	3.157 s
提交时间	2016-10-01 21:48:18	内存使用	15.57 MiB

/*
  Name: 遥远的国度
  Copyright: 
  Author: chairman
  Date: 01/10/16 18:58
  Description: 树剖,变根后不必重复dfs, 查询时分情况讨论
  			   如果root=x,则查询整棵树
			   如果lca(root,x)!=x,则查询x的子书
			   如果lca(root,x)==x,则找到root到x的路径上x的儿子,必须是最近的儿子(用倍增),然后查询整棵树中除这个儿子子树外的结点 
*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 101000
#define maxe 201000
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	int cnt=0;char ch[50];
	while(ch[++cnt]=x%10+48,x/=10);
	while(putchar(ch[cnt]),--cnt);
	putchar('\n');
}
struct edge
{
	int t,n;
}a[maxe];
int len,head[maxn];
void insert(int x,int y)
{
	a[++len].t=y;a[len].n=head[x];head[x]=len;
}
int D,n,m,size[maxn],son[maxn],fa[maxn][25],val[maxn],tp[maxn],dp[maxn],cnt,root,id[maxn],pos[maxn];
int ra[maxn<<2];
bool lazy[maxn<<2];
#define k a[i].t
void dfs1(int x)
{
	size[x]=1;
	for(int i=head[x];i;i=a[i].n)
	{
		if(fa[x][0]==k)continue;
		dp[k]=dp[x]+1;
		fa[k][0]=x;
		dfs1(k);
		size[x]+=size[k];
		if(size[son[x]]<size[k])son[x]=k;
	}
}
void dfs2(int x,int top)
{
	tp[x]=top;id[x]=++cnt;pos[cnt]=x;
	if(son[x])dfs2(son[x],top);
	for(int i=head[x];i;i=a[i].n)
	{
		if(fa[x][0]==k||son[x]==k)continue;
		dfs2(k,k);
	}
}
#undef k
void build(int rt,int l,int r)
{
	if(l==r)
	{
		ra[rt]=val[pos[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	ra[rt]=min(ra[rt<<1],ra[rt<<1|1]);
}
void update(int rt)
{
	ra[rt<<1]=ra[rt<<1|1]=ra[rt];
	lazy[rt]=0;
	lazy[rt<<1]=lazy[rt<<1|1]=1;
}
void change(int rt,int l,int r,int x,int y,int z)
{
	if(x<=l&&y>=r)
	{
		ra[rt]=z;
		lazy[rt]=1;
		return ;
	}
	if(lazy[rt])update(rt);
	int mid=(l+r)>>1;
	if(x<=mid)change(lson,x,y,z);
	if(y>mid)change(rson,x,y,z);
	ra[rt]=min(ra[rt<<1],ra[rt<<1|1]);
}
int query(int rt,int l,int r,int x,int y)
{
	if(x<=l&&y>=r)return ra[rt];
	if(lazy[rt])update(rt);
	int mid=(l+r)>>1;
	int ans=0x7f7f7f7f;
	if(x<=mid)ans=min(ans,query(lson,x,y));
	if(y>mid)ans=min(ans,query(rson,x,y));
	return ans;
}
int lca(int x,int y)
{
	int fx=tp[x],fy=tp[y];
	while(fx!=fy)
	{
		if(dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
		x=fa[fx][0];fx=tp[x];
	}
	if(dp[x]>dp[y])return y;
	else return x;
}
int find(int x,int y)
{
	for(int j=20;j>=0;j--)
		if(dp[fa[x][j]]>dp[y])x=fa[x][j];
	return x;
}
void tree_change(int x,int y,int z)
{
	int fx=tp[x],fy=tp[y];
	while(fx!=fy)
	{
		if(dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
		change(1,1,n,id[fx],id[x],z);
		x=fa[fx][0],fx=tp[x];
	}
	change(1,1,n,id[x],id[y],z);
}
int main()
{
	freopen("bbbbb.in","r",stdin);
	freopen("bbbbb.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		insert(x,y);
		insert(y,x);
	}
	for(int i=1;i<=n;i++)val[i]=read();
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	root=read();
	D=log(n*1.0)/log(2.0);
	for(int j=1;j<=D;j++)
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	for(int i=1;i<=m;i++)
	{
		int type=read();
		if(type==1)root=read();
		if(type==2)
		{
			int x=read(),y=read(),z=read();
			tree_change(x,y,z);
		}
		if(type==3)
		{
			int x=read();
			if(x==root)
				write(query(1,1,n,1,n));
			else
			{
				int f=lca(root,x);
				if(f!=x)write(query(1,1,n,id[x],id[x]+size[x]-1));
				else
				{
					int y=find(root,x);
					write(min(query(1,1,n,1,id[y]-1),query(1,1,n,id[y]+size[y],n)));
				}
			}
		}
	}
	//system("pause");
}