题目：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+5,M=N<<1,K=20;const ll INF=(1ll<<31); 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=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } ll rdl() { ll ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',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]=1;dep[cr]=dep[f]+1; 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>>1; ls=++tot;build(l,mid,ls); rs=++tot;build(mid+1,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]=0; } 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>>1;pshd(cr); if(L<=mid)mdfy(l,mid,ls,L,R,k); if(mid<R)mdfy(mid+1,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>>1;pshd(cr); if(mid<L)return query(mid+1,r,rs,L,R); if(R<=mid)return query(l,mid,ls,L,R); return Mn(query(l,mid,ls,L,R),query(mid+1,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(1,n,1,dfn[top[x]],dfn[x],k); x=fa[top[x]]; } if(dep[x]<dep[y])swap(x,y); mdfy(1,n,1,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(1,n,1,1,n); if(dfn[rt]>dfn[x]&&dfn[rt]<=tl[x]) { int d=fnd(rt,x); return Mn(query(1,n,1,1,dfn[d]-1),query(1,n,1,tl[d]+1,n)); } return query(1,n,1,dfn[x],tl[x]); } int main() { n=rdn();int Q=rdn(); for(int i=1,u,v;i<n;i++) u=rdn(),v=rdn(),add(u,v),add(v,u); for(int i=1;i<=n;i++)w[i]=rdl(); dfs(1,0);top[1]=1;dfsx(1); tot=1;build(1,n,1); rt=rdn();int op,x,y;ll k; while(Q--) { op=rdn();x=rdn(); if(op==1)rt=x; if(op==2) { y=rdn();k=rdl();mdfy(x,y,k); } if(op==3)printf("%lld ",query(x)); } return 0; }