考虑暴力树剖。那么修改路径和查询子树最小值非常简单。
对于换根当然不能真的给他转一下，我们只记录当前根是哪个。对于查询，如果查询点不在当前根到原根的路径上，显然换根是对答案没有影响的；如果是当前根，答案就是整棵树最小值，否则即是要查询该路径上的后代所在子树外的点的最小值，去掉这段区间就可以了。
#include#include #include #include #include #include using namespace std;#define N 100010#define int unsigned int#define inf 2147483649int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,root,p[N],a[N],t=0,cnt=0;int dfn[N],id[N],fa[N],son[N],deep[N],size[N],top[N];int L[N<<2],R[N<<2],tree[N<<2],lazy[N<<2];struct data{ int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs1(int k){ size[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]) { deep[edge[i].to]=deep[k]+1; fa[edge[i].to]=k; dfs1(edge[i].to); size[k]+=size[edge[i].to]; if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to; }}void dfs2(int k,int from){ id[k]=++cnt;dfn[cnt]=k; top[k]=from; if (son[k]) dfs2(son[k],from); for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) dfs2(edge[i].to,edge[i].to);}void build(int k,int l,int r){ L[k]=l,R[k]=r; if (l==r) {tree[k]=a[dfn[l]];return;} int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); tree[k]=min(tree[k<<1],tree[k<<1|1]);}void down(int k){ tree[k<<1]=tree[k<<1|1]=lazy[k]; lazy[k<<1]=lazy[k<<1|1]=lazy[k]; lazy[k]=0;}void up(int k){tree[k]=min(tree[k<<1],tree[k<<1|1]);}int query(int k,int l,int r){ if (l>r) return inf; if (L[k]==l&&R[k]==r) return tree[k]; if (lazy[k]) down(k); int mid=L[k]+R[k]>>1; if (r<=mid) return query(k<<1,l,r); else if (l>mid) return query(k<<1|1,l,r); else return min(query(k<<1,l,mid),query(k<<1|1,mid+1,r));}void modify(int k,int l,int r,int x){ if (L[k]==l&&R[k]==r) {tree[k]=lazy[k]=x;return;} if (lazy[k]) down(k); int mid=L[k]+R[k]>>1; if (r<=mid) modify(k<<1,l,r,x); else if (l>mid) modify(k<<1|1,l,r,x); else modify(k<<1,l,mid,x),modify(k<<1|1,mid+1,r,x); up(k);}void jump_modify(int x,int y,int z){ while (top[x]!=top[y]) { if (deep[top[x]]