玩原神玩多了 树剖换根求调

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
//ifstream fin("");
//ofstream fout("");
int n,m;
struct node{
	int to;
};
int u,v,opt,cap,w,x;
	struct nod3{
		int l,r;
		mutable int v;
		bool operator < (const nod3 &o) const{
			return l<o.l;
		} 
	};
	set <nod3 > tree;
namespace odt{	
	auto split(int pos){
		auto it=tree.lower_bound({pos,0,0});
		if(it->l==pos and it!=tree.end()) {return it;}
		--it;
		int l=it->l,r=it->r,v=it->v;
		tree.erase(it);
		tree.insert({l,pos-1,v});
		return tree.insert({pos,r,v}).first;
	}
	int querymin(int l,int r){
		int res=1e18;
		auto end=split(r+1);
		for(auto it=split(l);it!=end;it++){
			res=min(res,it->v);
		}
		return res;
	}
	void assign(int l,int r,int v){
		auto end=split(r+1),begin=split(l);
		tree.erase(begin,end);
		tree.insert({l,r,v});
	}
	
	void add(int l,int r,int v){
		auto end=split(r+1),begin=split(l);
		for(auto it=begin;it!=end;it++){
			it->v+=v;
		}
	}
}
vector <node > edge[1145141];
int init[1145141];
int dep[1145141],size[1145141],f[1145141],son[1145141],id[1145141],top[1145141],from[1145141],t0[1145141];
void dfs1(int u,int fa){
	dep[u]=dep[fa]+1;
	f[u]=fa;
	size[u]=1;
	
	int maxson=-1;
	for(auto e:edge[u]){
		if(e.to==fa) continue;
	//	from[e.id]=u;
	//	t0[e.id]=e.to;
	//	init[e.to]=e.w;//pushdown edge.w
		dfs1(e.to,u);
		size[u]+=size[e.to];
		if(size[e.to]>maxson){
			maxson=size[e.to];
			son[u]=e.to;
		}
	}
}

int cnt=0;
void dfs2(int u,int tp){
	id[u]=++cnt;
	top[u]=tp;
	tree.insert({id[u],id[u],init[u]});
	if(son[u]==0) return;
	
	dfs2(son[u],tp);
	for(auto e:edge[u]){
		if(e.to==f[u] or e.to ==son[u]) continue;
		//dfs2(son[e.to],tp);
		dfs2(e.to,e.to);
	}
}
void modify(int u,int v,int w){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]] ) swap(u,v);
		odt::assign(id[top[u]],id[u],w);
		u=f[top[u]];
	}
	odt::assign(min(id[u],id[v]),max(id[u],id[v]),w);
}

int f1nd(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		if(f[top[u]] == v) return top[u];
		u=f[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	return son[u];
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=f[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	return u;
}
int query(int x){
	int p=lca(x,cap);
	if(x==cap) return odt::querymin(1,n);
	if(p != x) return odt::querymin(id[x],id[x]+size[x]-1);
	else{
		int q=f1nd(x,cap);
		return min(odt::querymin(1, id[q]-1), odt::querymin(id[q] + size[q], cnt));
	}
	
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>n>>m;
	for(int i=0;i<n-1;i++){
		cin>>u>>v;
		edge[u].push_back({v});
		edge[v].push_back({u});
	}
	for(int i=1;i<=n;i++) cin>>init[i];
	cin>>cap;
	while(m--){
		cin>>opt;
		if(opt==1){
			cin>>cap;
		} else if(opt==2){
			cin>>u>>v>>w;
			modify(u,v,w);
		} else{
			cin>>x;
			query(x);
		}
	}
	return 0;
}