#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Max=3e5+10;
const int inf=3e9+10; 

struct node{
	int to,next;
}a[Max<<1]; 

int head[Max],cnt;
int val[Max];
int n,m;

void add(int x,int y){
	a[++cnt].to=y;
	a[cnt].next=head[x];
	head[x]=cnt;
}

struct tree{
	int size,son,top,dep,fa,id,rk;
	#define size(x) b[x].size
	#define son(x) b[x].son
	#define top(x) b[x].top
	#define dep(x) b[x].dep
	#define fa(x) b[x].fa
	#define id(x) b[x].id
	#define rk(x) b[x].rk
}b[Max];

void dfs1(int now,int fa){
	fa(now)=fa;
	dep(now)=dep(fa)+1;
	size(now)=1;
	for(int i=head[now];i;i=a[i].next){
		int to=a[i].to;
		if(to!=fa){
			dfs1(to,now);
			size(now)+=size(to);
			son(now)=size(son(now))>size(to)?son(now):to;
		}
	}
}

int pos=0;

void dfs2(int now,int top){
	top(now)=top;
	id(now)=++pos;
	rk(pos)=val[now];
	if(son(now))dfs2(son(now),top);
	for(int i=head[now];i;i=a[i].next){
		int to=a[i].to;
		if(!top(to)){
			dfs2(to,to);
		}
	}
}

struct tre{
	int minn=0,tag=0;
}tr[Max<<2];

void pushup(int now){
	tr[now].minn=min(tr[now<<1].minn,tr[now<<1|1].minn);
}

void solve(int now,int v){
	tr[now].tag=v;
	tr[now].minn=v;
}

void pushdown(int now){
	if(tr[now].tag){
		solve(now<<1,tr[now].tag);
		solve(now<<1|1,tr[now].tag);
		tr[now].tag=0;
	}
}

void build(int now,int l,int r){
	if(l==r){
		tr[now].minn=rk(l);
		return ;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	pushup(now);
}

void update(int now,int l,int r,int L,int R,int v){
	if(L<=l&&R>=r){
		solve(now,v);
		return;
	}
	pushdown(now);
	int mid=(l+r)>>1;
	if(L<=mid)update(now<<1,l,mid,L,R,v);
	if(R>mid) update(now<<1|1,mid+1,r,L,R,v);
	pushup(now);
}

int query(int now,int l,int r,int L,int R){
	if(L<=l&&R>=r){
		return tr[now].minn;
	}
	pushdown(now);
	int mid=(l+r)>>1,ans=inf;
	if(L<=mid)ans=min(ans,query(now<<1,l,mid,L,R));
	if(R>mid)ans=min(ans,query(now<<1|1,mid+1,r,L,R));
//	pushup(now);
	return ans;
}

int lca(int x,int y){
	while(top(x)!=top(y)){
		if(dep(top(x))<dep(top(y)))swap(x,y);
		x=fa(top(x));
	}
	if(dep(x)>dep(y))swap(x,y);
	return x;
}

void tree_update(int x,int y,int v){
	while(top(x)!=top(y)){
		if(dep(top(x))<dep(top(y)))swap(x,y);
		update(1,1,n,id(top(x)),id(x),v);
		x=fa(top(x));
	}
	if(dep(x)>dep(y))swap(x,y);
	update(1,1,n,id(x),id(y),v);
}

int root;

signed main(){
	scanf("%lld%lld",&n,&m);	
	for(int i=1;i<n;++i){
		int x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;++i){
		scanf("%lld",&val[i]);
	}
	scanf("%lld",&root);
	dfs1(root,root);
	dfs2(root,root);
	build(1,1,n);
	for(int i=1;i<=m;++i){
		int opt,x,y,v,id;
		scanf("%lld",&opt);
		if(opt==2){
			scanf("%lld%lld%lld",&x,&y,&v);
			tree_update(x,y,v);
			continue;
		}
		scanf("%lld",&id);
		if(opt==1){
			root=id;
			continue;
		}
		if(id==root){
			printf("%lld\n",query(1,1,n,1,n));
			continue;
		}
		int lc=lca(root,id);
		if(lc!=id){
			printf("%lld\n",query(1,1,n,id(id),id(id)+size(id)-1));
		}else{
			int ans=query(1,1,n,1,id(id));
			ans=min(ans,query(1,1,n,id(id)+size(id),n));
			int ta=0;
			for(int z=head[id];z;z=a[z].next){
				int to=a[z].to;
				if(to==fa(id))continue;
				if(ta){
					ans=min(ans,query(1,1,n,id(to),id(to)+size(to)-1));
				}else{
					int p=lca(to,root);
					if(p==to){
						ta=1;
					}else{
						ans=min(ans,query(1,1,n,id(to),id(to)+size(to)-1));	
					}
				}
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

原代码中query()函数加上pushup会wa #5 和 #10

但是删除后AC

为什么？

int query(int now,int l,int r,int L,int R){
	if(L<=l&&R>=r){
		return tr[now].minn;
	}
	pushdown(now);
	int mid=(l+r)>>1,ans=inf;
	if(L<=mid)ans=min(ans,query(now<<1,l,mid,L,R));
	if(R>mid)ans=min(ans,query(now<<1|1,mid+1,r,L,R));
//	pushup(now);
	return ans;
}

（注：请求加强数据，本人做法最坏 $\mathcal O(nm \ log \ n)$ 但AC）