解题思路
前两个操作都比较基础。对于第三个操作分类讨论一下，首先如果当前根不是要操作点的子树，那么就无影响，直接查询操作点的子树即可。第二种是当前根是操作点的子树，那就找到当前根到操作点这条链的顶端(也就是操作点的儿子，这个儿子为当前根的祖先)，然后将这块连续的(dfs)序挖掉，查询两边就行了。找这个点的时候用倍增即可。(暴力往上跳也能过)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int MAXN = 100005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,m,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1],w[MAXN],wt[MAXN],rt,num,g[MAXN][20];
int siz[MAXN],fa[MAXN],son[MAXN],id[MAXN],Min[MAXN<<2],tag[MAXN<<2],top[MAXN],dep[MAXN];
inline int min(int x,int y){
return x<y?x:y;
}
inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}
void dfs1(int x,int f,int d){
dep[x]=d;fa[x]=f;siz[x]=1;g[x][0]=f;
for(int i=1;i<=18;i++) g[x][i]=g[g[x][i-1]][i-1];
int maxson=-1,u;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==f) continue;
dfs1(u,x,d+1);siz[x]+=siz[u];
if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}
}
}
void dfs2(int x,int topf){
id[x]=++num;wt[num]=w[x];
top[x]=topf;if(!son[x]) return;
dfs2(son[x],topf);int u;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==fa[x] || u==son[x]) continue;
dfs2(u,u);
}
}
void build(int x,int l,int r){
if(l==r) {Min[x]=wt[l];return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
Min[x]=min(Min[x<<1],Min[x<<1|1]);
}
inline void pushdown(int x){
Min[x<<1]=tag[x];Min[x<<1|1]=tag[x];
tag[x<<1]=tag[x];tag[x<<1|1]=tag[x];
tag[x]=0;
}
void update(int x,int l,int r,int L,int R,int k){
if(L<=l && r<=R) {Min[x]=k;tag[x]=k;return;}
int mid=(l+r)>>1;if(tag[x]) pushdown(x);
if(L<=mid) update(x<<1,l,mid,L,R,k);
if(mid<R) update(x<<1|1,mid+1,r,L,R,k);
Min[x]=min(Min[x<<1],Min[x<<1|1]);
}
int query(int x,int l,int r,int L,int R){
if(L<=l && r<=R) return Min[x];
int mid=(l+r)>>1,ret=0x7fffffff;if(tag[x]) pushdown(x);
if(L<=mid) ret=min(ret,query(x<<1,l,mid,L,R));
if(mid<R) ret=min(ret,query(x<<1|1,mid+1,r,L,R));
return ret;
}
inline void updRange(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(1,1,n,id[top[x]],id[x],k);x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);update(1,1,n,id[x],id[y],k);
}
inline int qRange(int x,int y){
if(fa[x]==y) return x;
for(int i=18;i>=0;i--){
if(fa[g[x][i]]==y) return g[x][i];
if(dep[fa[g[x][i]]]>dep[y]) x=g[x][i];
}
return x;
}
inline int qSon(int x){
if(x==rt) return query(1,1,n,1,n);
if(id[rt]>id[x]+siz[x]-1 || id[rt]<id[x]) return query(1,1,n,id[x],id[x]+siz[x]-1);
int point=qRange(rt,x),ret=0x7fffffff;
if(id[point]+siz[point]<=n) ret=min(ret,query(1,1,n,id[point]+siz[point],n));
if(id[point]-1>=1) ret=min(ret,query(1,1,n,1,id[point]-1));return ret;
}
int main(){
n=rd(),m=rd();int x,y,op,z;
for(int i=1;i<n;i++){
x=rd(),y=rd();
add(x,y),add(y,x);
}
for(int i=1;i<=n;i++) w[i]=rd();rt=rd();
dfs1(rt,0,1);dfs2(rt,rt);build(1,1,n);
while(m--){
op=rd();
if(op==1) x=rd(),rt=x;
if(op==2){
x=rd(),y=rd(),z=rd();
updRange(x,y,z);
}
if(op==3) {x=rd();printf("%d
",qSon(x));}
}
return 0;
}