mx求调树剖80pts,WAon7&10

#include <bits/stdc++.h>

using namespace std;
#define N 100100
#define ls (p<<1)
#define rs (p<<1|1)

const int inf = 2e9;
int n,m,rt,v[N];
int dep[N],f[N],s[N],siz[N],son[N],cnt,a[N],tp[N],id[N];
vector<int> e[N];
struct Segtree{
	int l,r,Min,tag;
}t[N<<2];

void dfs(int x,int fa){
	f[x]=fa,s[fa]=x,siz[x]=1;
	dep[x]=dep[fa]+1;
	for(int i=0;i<e[x].size();i++){
		int y=e[x][i];
		if(y== fa) continue;
		dfs(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]])
			son[x]=y;
	}
}

void dfs2(int x,int top){
	tp[x]=top;
	id[x]=++cnt;
	a[id[x]]=x;
	if(son[x]) dfs2(son[x],top);
	for(int i=0;i<e[x].size();i++)
		if(e[x][i]!=f[x] && e[x][i]!=son[x])
			dfs2(e[x][i],e[x][i]);
}

void pushup(int p){
	t[p].Min=min(t[ls].Min,t[rs].Min);
}
void pushdown(int p){
	if(!t[p].tag) return ;
	t[ls].Min=t[p].tag;
	t[rs].Min=t[p].tag;
	t[ls].tag=t[p].tag;
	t[rs].tag=t[p].tag;
	t[p].tag=0;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].Min=inf;
	if(l==r){
		t[p].Min=v[a[l]],t[p].tag=0;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}

void update(int p,int l,int r,int v){
	if(l<=t[p].l && r>=t[p].r){
		t[p].tag=t[p].Min=v;
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) update(ls,l,r,v);
	if(r>mid) update(rs,l,r,v);
	pushup(p);
}

int query(int p,int l,int r){
	if(l<=t[p].l && r>=t[p].r) return t[p].Min;
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	int ans=inf;
	if(l<=mid) ans=min(ans,query(ls,l,r));
	if(r>mid) ans=min(ans,query(rs,l,r));
	pushup(p);
	return ans;
}

void updatelink(int x,int y,int v){
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]>dep[tp[y]]){
			update(1,id[tp[x]],id[x],v);
			x=f[tp[x]];
		}else{
			update(1,id[tp[y]],id[y],v);
			y=f[tp[y]];
		}
	}
	if(dep[x]>dep[y]) swap(x,y);
	update(1,id[x],id[y],v);
}

int glca(int x,int y){
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]>dep[tp[y]]) x=f[tp[x]];
		else y=f[tp[y]];
	}
	if(dep[x]<dep[y]) return x;
	else return y;
}

void que(int x){
	int lca=glca(x,rt);
	if(lca==rt) cout<<query(1,id[x],id[x]+siz[x]-1)<<endl;
	else if(lca==x){
		int l=id[s[x]],r=id[s[x]]+siz[s[x]]-1;
		if(l>r) return;
		if(l>1 && r<n) cout<<min(query(1,1,l-1),query(1,r+1,n))<<endl;
		else if(l==1 && r<n) cout<<query(1,r+1,n)<<endl;
		else if(l>1 && r<=n) cout<<query(1,1,l-1)<<endl;
	}else cout<<query(1,id[x],id[x]+siz[x]-1)<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v; cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;i++) cin>>v[i];
	dfs(1,1);
	dfs2(1,1);
	build(1,1,n);
	int id; cin>>id; rt=id;
	while(m--){
		int opt,id,x,y,v; cin>>opt;
		if(opt==1) {
			cin>>id;
			rt=id;
		}else if(opt==2){
			cin>>x>>y>>v;
			updatelink(x,y,v);
		}else{
			cin>>id;
			que(id);
		}
	}
	return 0;
}