题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3083
int 的范围是 2^31 - 1 ，所以权值是不是爆 int 了……
O( nlog2n ) 也能过？
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
const int N=1e5+,M=N<<,K=;const ll INF=(1ll<<);
int n,hd[N],xnt,to[M],nxt[M],rt; ll w[N];
int dfn[N],rnk[N],tl[N],siz[N],son[N],fa[N],top[N],dep[N];
int tot,Ls[M],Rs[M]; ll sm[M],tg[M];
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
ll rdl()
{
ll ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
ll Mn(ll a,ll b){return a<b?a:b;}
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void dfs(int cr,int f)
{
fa[cr]=f;siz[cr]=;dep[cr]=dep[f]+;
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=f)
{
dfs(v,cr);siz[cr]+=siz[v];
if(siz[v]>siz[son[cr]])son[cr]=v;
}
}
void dfsx(int cr)
{
dfn[cr]=++tot;rnk[tot]=cr;
if(son[cr])top[son[cr]]=top[cr],dfsx(son[cr]);
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa[cr]&&v!=son[cr])
top[v]=v,dfsx(v);
tl[cr]=tot;
}
void build(int l,int r,int cr)
{
if(l==r){sm[cr]=w[rnk[l]];return;}
int mid=l+r>>;
ls=++tot;build(l,mid,ls);
rs=++tot;build(mid+,r,rs);
sm[cr]=Mn(sm[ls],sm[rs]);
}
void pshd(int cr)
{
if(!tg[cr])return;
tg[ls]=tg[rs]=sm[ls]=sm[rs]=tg[cr];tg[cr]=;
}
void mdfy(int l,int r,int cr,int L,int R,ll k)
{
if(l>=L&&r<=R){sm[cr]=tg[cr]=k;return;}
int mid=l+r>>;pshd(cr);
if(L<=mid)mdfy(l,mid,ls,L,R,k);
if(mid<R)mdfy(mid+,r,rs,L,R,k);
sm[cr]=Mn(sm[ls],sm[rs]);
}
ll query(int l,int r,int cr,int L,int R)
{
if(L>R)return INF;//don't forget!!!
if(l>=L&&r<=R)return sm[cr];
int mid=l+r>>;pshd(cr);
if(mid<L)return query(mid+,r,rs,L,R);
if(R<=mid)return query(l,mid,ls,L,R);
return Mn(query(l,mid,ls,L,R),query(mid+,r,rs,L,R));
}
void mdfy(int x,int y,ll k)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
mdfy(,n,,dfn[top[x]],dfn[x],k);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
mdfy(,n,,dfn[y],dfn[x],k);
}
int fnd(int x,int f)
{
while(dep[fa[top[x]]]>dep[f])x=fa[top[x]];
if(dep[fa[top[x]]]==dep[f])return top[x];
return son[f];
}
ll query(int x)
{
if(rt==x)return query(,n,,,n);
if(dfn[rt]>dfn[x]&&dfn[rt]<=tl[x])
{
int d=fnd(rt,x);
return Mn(query(,n,,,dfn[d]-),query(,n,,tl[d]+,n));
}
return query(,n,,dfn[x],tl[x]);
}
int main()
{
n=rdn();int Q=rdn();
for(int i=,u,v;i<n;i++)
u=rdn(),v=rdn(),add(u,v),add(v,u);
for(int i=;i<=n;i++)w[i]=rdl();
dfs(,);top[]=;dfsx();
tot=;build(,n,);
rt=rdn();int op,x,y;ll k;
while(Q--)
{
op=rdn();x=rdn();
if(op==)rt=x;
if(op==)
{
y=rdn();k=rdl();mdfy(x,y,k);
}
if(op==)printf("%lld\n",query(x));
}
return ;
}