P3979 【遥远的国度】

这道题看起来像一道树剖~~（显然就是树剖）~~ 与普通树剖不同的地方在于有一种操作叫换根 然而我们并不能在换根的时候重构整棵树~~（显然会T）~~ 所以就需要考虑其他对策（分类讨论！） 一开始先以1为根把树建好 然后再查询子树最小值时，可以发现 如果当前根节点不在查询的子树中，它对这棵子树是没有影响的 所以就查询idx[x]到idx[x]+tot[x]-1就好了 但如果根节点在查询的这棵子树中， 那我们真正要查询的子树其实是原子树去掉根节点所在的部分以外的部分 ~~（好像有点拗口）~~具体见代码 这个题的精髓也就在这里了，其余操作同树剖模板 丑陋的代码： ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; const int N=1e5+5; struct edge { int to,nxt; }edge[N<<1]; int n,q,num,head[N],w[N],fa[N],son[N],tot[N]; int root,cnt,idx[N],top[N],dep[N],a[N]; int minn[N<<2],tag[N<<2]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num].nxt=head[from]; edge[num].to=to; head[from]=num; } void dfs(int k,int father,int deep) { int bigson=0; fa[k]=father; dep[k]=deep; tot[k]=1; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==father) continue; dfs(v,k,deep+1); tot[k]+=tot[v]; if (bigson<tot[v]) { bigson=tot[v]; son[k]=v; } } } void dfs(int k,int tp) { idx[k]=++cnt; top[k]=tp; a[cnt]=w[k]; if (!son[k]) return; dfs(son[k],tp); for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (!idx[v]) dfs(v,v); } } inline void pushup(int now) { minn[now]=min(minn[now<<1],minn[now<<1|1]); } inline void pushdown(int now) { if (tag[now]==-1) return; tag[now<<1]=tag[now<<1|1]=tag[now]; minn[now<<1]=minn[now<<1|1]=tag[now]; tag[now]=-1; } void build(int l,int r,int now) { tag[now]=-1; if (l==r) { minn[now]=a[l]; return; } int mid=(l+r)>>1; build(l,mid,now<<1); build(mid+1,r,now<<1|1); pushup(now); } void inchange(int L,int R,int l,int r,int now,int c) { if (l>R||r<L) return; if (l>=L&&r<=R) { minn[now]=c; tag[now]=c; return; } int mid=(l+r)>>1; pushdown(now); if (mid>=R) inchange(L,R,l,mid,now<<1,c); else if (mid<L) inchange(L,R,mid+1,r,now<<1|1,c); else { inchange(L,mid,l,mid,now<<1,c); inchange(mid+1,R,mid+1,r,now<<1|1,c); } pushup(now); } int getmin(int L,int R,int l,int r,int now) { if (l>R||r<L) return 2e9; if (l>=L&&r<=R) return minn[now]; int mid=(l+r)>>1; pushdown(now); if (mid>=R) return getmin(L,R,l,mid,now<<1); if (mid<L) return getmin(L,R,mid+1,r,now<<1|1); return min(getmin(L,mid,l,mid,now<<1),getmin(mid+1,R,mid+1,r,now<<1|1)); } inline void treechange(int x,int y,int val) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); inchange(idx[top[x]],idx[x],1,n,1,val); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); inchange(idx[x],idx[y],1,n,1,val); } inline bool check(int root,int v) { return idx[root]>=idx[v]&&idx[root]<=idx[v]+tot[v]-1; } int main() { n=read(),q=read(); for (reg int i=1;i<n;i++) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } for (reg int i=1;i<=n;w[i++]=read()); dfs(1,0,1); dfs(1,1); build(1,n,1); for (root=read();q;q--) { int opt=read(); if (opt==1) root=read(); if (opt==2) { int x=read(),y=read(),z=read(); treechange(x,y,z); } if (opt==3) { int x=read(); if (x==root) printf("%d\n",minn[1]); else { int now=0; for (reg int i=head[x];i&&!now;i=edge[i].nxt) { int v=edge[i].to; if (v==fa[x]) continue; if (check(root,v)) now=v; } if (now) { int l=getmin(1,idx[now]-1,1,n,1),r=2e9; if (idx[now]+tot[now]<=n) r=getmin(idx[now]+tot[now],n,1,n,1); int ans=getmin(idx[x],idx[x],1,n,1); printf("%d\n",min(ans,min(l,r))); } else printf("%d\n",getmin(idx[x],idx[x]+tot[x]-1,1,n,1)); } } } } ```