题意：懂得都懂。
首先考虑到这题如果没有换根的操作，那么很显然就是一个裸的树剖部分，那么随便搞搞就能过了。
对于加上了换根的操作。
我们来对询问进行一个分类讨论。
我们统一以1为根来建树：
如果当前的询问的点等于根，那么显然就是全局最小值，就是node[1].mi。
如果当前的询问的点在不在1->root的链上，那么询问他的子树里的最小值也和1为根时一样。
因为root和1必定都是从他的一边来建树，所以不影响（可以画图理解下）
如果当前询问的点在1->root的链上：（即LCA(x,root == x）
那么以（x对于root方向的第一个子节点z）为根的子树，都不可能是它的子树。
那么剩下的就都是了。（这点也可以画图理解下）
所以我们只需要找到这个第一个点，同时由于树剖建的线段树上的dfs序关于子树内都是连续的。
那么我们既可以很容易地找到我们要删去的区间为[id[z],id[z]+ssize[z]-1]。
那么我们要查询的区间显然就是[1,id[z]-1] && [id[z]+ssize[z],n]。
那么如何找到这个z呢。暴力走肯定会T。
这里用了倍增来找。可以发现对于这个点z，就是root向上dep[root]-dep[x]-1的倍增位置。
所以从大的开始一直倍增跳就行了
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef long double ld; typedef pair<LL,int> pii; const int N = 1e5+5; const int M = 1e6+5; const LL Mod = 998244353; #define rg register #define pi acos(-1) #define INF 1e18 #define INM INT_MIN #define dbg(ax) cout << "now this num is " << ax << endl; inline LL read() { LL 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; } vector<int> G[N]; int dep[N],f[N][25],rk[N],ssize[N],id[N],lg[N],son[N],top[N],tim = 0,root; LL val[N]; struct Node{int L,r;LL tag,mi;}node[N<<2]; void Pushdown(int idx) { if(node[idx].tag != 0) { int tag = node[idx].tag; node[idx<<1].mi = node[idx<<1|1].mi = tag; node[idx<<1].tag = node[idx<<1|1].tag = tag; node[idx].tag = 0; } } void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r,node[idx].tag = 0; if(L == r) { node[idx].mi = val[rk[L]]; return ; } int mid = (L+r)>>1; build(L,mid,idx<<1); build(mid+1,r,idx<<1|1); node[idx].mi = min(node[idx<<1].mi,node[idx<<1|1].mi); } void update(int L,int r,int idx,LL x) { if(node[idx].L >= L && node[idx].r <= r) { node[idx].mi = node[idx].tag = x; return ; } Pushdown(idx); int mid = (node[idx].L+node[idx].r)>>1; if(mid >= L) update(L,r,idx<<1,x); if(mid < r) update(L,r,idx<<1|1,x); node[idx].mi = min(node[idx<<1].mi,node[idx<<1|1].mi); } LL query(int L,int r,int idx) { if(node[idx].L >= L && node[idx].r <= r) return node[idx].mi; Pushdown(idx); int mid = (node[idx].L+node[idx].r)>>1; LL minn = INF; if(mid >= L) minn = min(minn,query(L,r,idx<<1)); if(mid < r) minn = min(minn,query(L,r,idx<<1|1)); return minn; } void init() { for(int i = 1;i < N;++i) lg[i] = lg[i-1] + ((1<<lg[i-1]) == i); } void dfs(int u,int fa) { dep[u] = dep[fa]+1; f[u][0] = fa,ssize[u] = 1; for(int i = 1;i <= lg[dep[u]];++i) f[u][i] = f[f[u][i-1]][i-1]; for(auto v : G[u]) { if(v == fa) continue; dfs(v,u); ssize[u] += ssize[v]; if(ssize[v] > ssize[son[u]]) son[u] = v; } } void dfs1(int u,int sta) { id[u] = ++tim; rk[tim] = u; top[u] = sta; if(son[u] == 0) return ; dfs1(son[u],sta); for(auto v : G[u]) if(v != f[u][0] && v != son[u]) dfs1(v,v); } void Tree_update(int x,int y,LL val) { while(top[x] != top[y])//未在同一条链上 { if(dep[top[x]] < dep[top[y]]) swap(x,y); update(id[top[x]],id[x],1,val); x = f[top[x]][0]; } if(dep[x] > dep[y]) swap(x,y); update(id[x],id[y],1,val); } int LCA(int x,int y) { if(dep[x] < dep[y]) swap(x,y); while(dep[x] > dep[y]) { x = f[x][lg[dep[x]-dep[y]]-1]; } if(x == y) return x; for(rg int i = lg[dep[x]]-1;i >= 0;--i) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i]; return f[x][0]; } int Get_fa(int x,int k) { for(int i = 24;i >= 0;--i) { if(k >= (1<<i)) { x = f[x][i]; k -= (1<<i); } } return x; } int main() { init(); int n,m;n = read(),m = read(); for(rg int i = 1;i < n;++i) { int x,y;x = read(),y = read(); G[x].push_back(y); G[y].push_back(x); } for(rg int i = 1;i <= n;++i) val[i] = read(); root = read(); dfs(1,0); dfs1(1,1); build(1,tim,1); while(m--) { int opt,x,y;LL v;opt = read(); if(opt == 1) root = read(); else if(opt == 2) { x = read(),y = read(),v = read(); Tree_update(x,y,v); } else { x = read(); if(x == root) printf("%lld\n",node[1].mi); else if(x != LCA(x,root)) printf("%lld\n",query(id[x],id[x]+ssize[x]-1,1)); else { int xx = Get_fa(root,dep[root]-dep[x]-1); LL ans = INF; if(id[xx]-1 >= 1) ans = min(ans,query(1,id[xx]-1,1)); if(id[xx]+ssize[xx] <= n) ans = min(ans,query(id[xx]+ssize[xx],n,1)); printf("%lld\n",ans); } } } system("pause"); return 0; } /* 10 15 1 2 1 3 3 6 6 9 2 4 2 5 4 7 4 8 7 10 3 3 2 1 4 5 6 2 3 7 2 3 2 3 5 1 3 3 2 3 6 1 7 3 6 3 10 2 1 5 10 3 7 3 1 */