由于懒得重打一遍直接贴上一题的剖分模板，结果因为上一题是单点查询所以一直T，T了5发才发现我是有多sb。。
明显不能直接换根，不然我全部操作都是换根你不就炸了。 假设开始的时候root，现在的根是newroot，查询的是x,那么明显有: 1.如果x=newroot，查询全部 2.如果newroot在x外，不受影响，直接查。 3.newroot在x内，查询x子树以外的，即1–pos[x]-1和mxpos[x]+1–n
#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define inf 0x7fffffff using namespace std; const int N=1e5+5; int n,m; int head[N<<1],next[N<<1],go[N<<1]; int siz[N],dep[N],fa[N][20]; int pos[N],top[N],a[N],mxpos[N]; int tot=0,sz; struct node { int l,r,mn,lazy; }t[1000000]; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } inline void build(int x,int l,int r) { t[x].l=l,t[x].r=r; t[x].mn=inf; if (l==r)return; int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } inline void pushdown(int x) { if (t[x].l==t[x].r)return; if (t[x].lazy) { t[x<<1].lazy=t[x<<1|1].lazy=t[x<<1].mn=t[x<<1|1].mn=t[x].lazy; t[x].lazy=0; } } inline void pushup(int x) { t[x].mn=min(t[x<<1].mn,t[x<<1|1].mn); } inline void change(int x,int l,int r,int z) { pushdown(x); if (t[x].l==l&&t[x].r==r) { t[x].lazy=t[x].mn=z; return; } int mid=(t[x].l+t[x].r)>>1; if (r<=mid)change(x<<1,l,r,z); else if (l>mid)change(x<<1|1,l,r,z); else { change(x<<1,l,mid,z); change(x<<1|1,mid+1,r,z); } pushup(x); } inline void dfs1(int x) { fo(i,1,16) if (fa[x][i-1])fa[x][i]=fa[fa[x][i-1]][i-1]; siz[x]=1; for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x][0]) { dep[v]=dep[x]+1; fa[v][0]=x; dfs1(v); siz[x]+=siz[v]; } } } inline void dfs2(int x,int chain) { int k=0; sz++; pos[x]=sz; top[x]=chain; mxpos[x]=sz; change(1,sz,sz,a[x]); for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x][0]&&siz[v]>siz[k]) k=v; } if (!k)return; dfs2(k,chain); mxpos[x]=max(mxpos[x],mxpos[k]); for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x][0]&&k!=v) { dfs2(v,v); mxpos[x]=max(mxpos[x],mxpos[v]); } } } inline int query(int x,int l,int r) { pushdown(x); if (t[x].l==l&&t[x].r==r)return t[x].mn; int mid=(t[x].l+t[x].r)>>1; if (r<=mid)return query(x<<1,l,r); else if (l>mid)return query(x<<1|1,l,r); else return min(query(x<<1,l,mid),query(x<<1|1,mid+1,r)); } inline void solve(int x,int y,int z) { while(top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]])swap(x,y); change(1,pos[top[x]],pos[x],z); x=fa[top[x]][0]; } if (dep[x]<dep[y])swap(x,y); change(1,pos[y],pos[x],z); } inline int getlca(int x,int y) { if (dep[x]<dep[y])swap(x,y); fd(i,16,0) if (dep[fa[x][i]]>=dep[y])x=fa[x][i]; if (x==y)return x; fd(i,16,0) if (fa[x][i]!=fa[y][i]) { x=fa[x][i],y=fa[y][i]; } return fa[x][0]; } int getv(int x,int y) { fd(i,16,0) if (dep[fa[x][i]]>dep[y])x=fa[x][i]; return x; } inline int solveq(int x,int root) { if (x==root)return query(1,1,n); if (getlca(x,root)!=x)return query(1,pos[x],mxpos[x]); int v=getv(root,x),ans=inf; if (pos[v]>1)ans=min(ans,query(1,1,pos[v]-1)); if (mxpos[v]<n)ans=min(ans,query(1,mxpos[v]+1,n)); return ans; } int main() { scanf("%d%d",&n,&m); fo(i,1,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } build(1,1,n); fo(i,1,n)scanf("%d",&a[i]); int root; scanf("%d",&root); dep[root]=1; dfs1(root); dfs2(root,root); int nowroot=root; fo(i,1,m) { int id; scanf("%d",&id); if (id==1) { int x; scanf("%d",&x); nowroot=x; } else if (id==2) { int x1,x2,v; scanf("%d%d%d",&x1,&x2,&v); solve(x1,x2,v); } else { int x; scanf("%d",&x); printf("%d\n",solveq(x,nowroot)); } } }