BZOJ100题辣（已经无法直视的正确率
树剖板子题，注意和dfs序结合，根据根的变化变换统计的方式即可。
//BZOJ 3083
//by Cydiater
//2016.10.23
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
#define ll long long
#define up(i,j,n) for( int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "bbbbb"
const int MAXN=1e5+5;
const ll oo=1LL<<32;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,dep[MAXN],LINK[MAXN],len=0,fa[MAXN][25],son[MAXN],siz[MAXN],top[MAXN],seg[MAXN],cnt=0,pos[MAXN],ROOT,opt,L,R;
ll v,pro[MAXN];
int c=0;
struct edge{
int y,next;
}e[MAXN<<1];
struct Tree{
ll v,delta;
}t[MAXN<<3];
namespace solution{
inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
inline void reload(int root){t[root].v=min(t[root<<1].v,t[root<<1|1].v);}
inline void downit(int root){
if(t[root].delta==0)return;
int delta=t[root].delta;t[root].delta=0;
t[root<<1].delta=delta;t[root<<1].v=delta;
t[root<<1|1].delta=delta;t[root<<1|1].v=delta;
}
void init(){
N=read();M=read();
up(i,2,N){
int x=read(),y=read();
insert(x,y);
insert(y,x);
}
up(i,1,N)pro[i]=read();
ROOT=read();
}
void dfs1(int node,int deep,int father){
fa[node][0]=father;dep[node]=deep;son[node]=0;
siz[node]=1;int max_siz=0;
for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=father){
dfs1(e[i].y,deep+1,node);
siz[node]+=siz[e[i].y];
if(siz[e[i].y]>max_siz){
max_siz=siz[e[i].y];
son[node]=e[i].y;
}
}
}
void dfs2(int node,int TOP){
top[node]=TOP;seg[++cnt]=node;pos[node]=cnt;
if(son[node])dfs2(son[node],TOP);
for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa[node][0]&&e[i].y!=son[node])
dfs2(e[i].y,e[i].y);
}
void get_ancestor(){
up(i,1,21)up(node,1,N)if(fa[node][i-1]!=0)
fa[node][i]=fa[fa[node][i-1]][i-1];
}
void build(int leftt,int rightt,int root){
if(leftt==rightt){
t[root].delta=0;
t[root].v=pro[seg[leftt]];
return;
}
int mid=(leftt+rightt)>>1;
build(leftt,mid,root<<1);
build(mid+1,rightt,root<<1|1);
reload(root);
}
void Build(){
dfs1(ROOT,0,0);dfs2(ROOT,ROOT);
get_ancestor();
build(1,N,1);
}
int LCA(int x,int y){
if(x==y) return x;
if(dep[x]<dep[y])swap(x,y);
down(i,21,0)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
if(x==y) return x;
down(i,21,0)if(fa[x][i]!=0&&fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
}
void updata(int leftt,int rightt,int root){
downit(root);
if(leftt>R||rightt<L) return;
if(leftt>=L&&rightt<=R){
t[root].delta=t[root].v=v;
return;
}
int mid=(leftt+rightt)>>1;
updata(leftt,mid,root<<1);
updata(mid+1,rightt,root<<1|1);
reload(root);
}
void change(int x,int aim){
while(top[x]!=top[aim]){
R=pos[x];L=pos[top[x]];
updata(1,N,1);
x=fa[top[x]][0];
}
R=pos[x];L=pos[aim];
updata(1,N,1);
}
void Change(int x,int y){
int lca=LCA(x,y);
change(x,lca);change(y,lca);
}
ll get(int leftt,int rightt,int root){
downit(root);
if(leftt>R||rightt<L) return oo;
if(leftt>=L&&rightt<=R) return t[root].v;
int mid=(leftt+rightt)>>1;
return min(get(leftt,mid,root<<1),get(mid+1,rightt,root<<1|1));
}
void slove(){
while(M--){
opt=read();
if(opt==1)ROOT=read();
else if(opt==2){
int x=read(),y=read();v=read();
Change(x,y);
}else{
int node=read(),Pos=pos[ROOT];ll ans;
int leftt=pos[node],rightt=leftt+siz[node]-1;
if(Pos==leftt){
L=1;R=N;
ans=get(1,N,1);
}else if(!(Pos>=leftt&&Pos<=rightt)){
L=leftt;R=rightt;
ans=get(1,N,1);
}else{
for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa[node][0]){
leftt=pos[e[i].y];rightt=pos[e[i].y]+siz[e[i].y]-1;
if(Pos>=leftt&&Pos<=rightt){
L=1;R=leftt-1;
if(R>=L)ans=get(1,N,1);
L=rightt+1,R=N;
if(L<=R)ans=min(ans,get(1,N,1));
break;
}
}
}
printf("%lld\n",ans);
}
}
}
}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
//freopen("input.in","r",stdin);
//freopen("out.out","w",stdout);
using namespace solution;
init();
Build();
slove();
return 0;
}