看上去是一个需要支持换根的数据结构.
用 $\mathrm{LCT}$ 来做肯定是可以的.
但是需要对每一个点的虚儿子们开一个 $\mathrm{set}$, 然后维护子树信息,相对麻烦.
不妨用树链剖分来做:
假设当前根为 $\mathrm{root}$, 要查询的点为 $\mathrm{x}$.
不难发现只需分 3 种情况讨论.
1. $\mathrm{x=root}$.
2. $\mathrm{lca(x,root)=x}$.
3. $\mathrm{others}$.
情况 $1, 3$ 都很好处理,情况而的话发现 $\mathrm{root}$ 到 $\mathrm{x}$ 路径上倒数第二个点的子树不行.
用 $\mathrm{DFS}$ 序加上树链剖分处理一下即可.
#include <cstdio> #include <cstring> #include <set> #include <map> #include <algorithm> #include <vector> #define N 100004 #define ls now<<1 #define rs now<<1|1 #define ll long long #define pb push_back #define setIO(s) freopen(s".in","r",stdin) using namespace std; const int inf=2000000000; int n,m,val[N],root; vector<int>G[N]; int fa[N],dep[N],st[N],ed[N],size[N],bu[N],son[N],scc; int mn[N<<2], lazy[N<<2], tag[N<<2], top[N]; void dfs1(int x,int ff) { fa[x]=ff,dep[x]=dep[ff]+1; size[x]=1; for(int i=0;i<G[x].size();++i) { int v=G[x][i]; if(v==ff) continue; dfs1(v, x); size[x]+=size[v]; if(size[v] > size[son[x]]) { son[x] = v; } } } void dfs2(int x,int tp) { top[x]=tp; st[x]=++scc; bu[st[x]]=x; if(son[x]) { dfs2(son[x], tp); } for(int i=0;i<G[x].size();++i) { int v=G[x][i]; if(v==son[x] || v==fa[x]) { continue; } dfs2(v, v); } ed[x]=scc; } void pushup(int now) { mn[now]=min(mn[ls], mn[rs]); } void build(int l, int r, int now) { lazy[now]=tag[now]=0; if(l == r) { mn[now]=val[bu[l]]; return ; } int mid=(l+r)>>1; build(l, mid, ls); build(mid+1, r, rs); pushup(now); } void mark(int now,int v) { mn[now]=v; tag[now]=1, lazy[now]=v; } void pushdown(int now) { if(tag[now]) { mark(ls, lazy[now]); mark(rs, lazy[now]); tag[now]=lazy[now]=0; } } void update(int l,int r,int now,int L,int R,int v) { if(l>=L&&r<=R) { mark(now, v); return ; } pushdown(now); int mid=(l+r)>>1; if(L<=mid) update(l,mid,ls,L,R,v); if(R>mid) update(mid+1,r,rs,L,R,v); pushup(now); } int query(int l,int r,int now,int L,int R) { if(l>=L&&r<=R) { return mn[now]; } pushdown(now); int mid=(l+r)>>1; if(L<=mid && R > mid) return min(query(l, mid, ls, L, R), query(mid+1,r,rs,L,R)); else if(L<=mid) return query(l,mid,ls,L,R); else return query(mid+1,r,rs,L,R); } void upd(int x,int y,int z) { while(top[x] != top[y]) { if(dep[top[x]] > dep[top[y]]) { swap(x, y); } // y = fa[top[y]]; update(1, n, 1, st[top[y]], st[y], z); y = fa[top[y]]; } if(dep[x] > dep[y]) swap(x, y); update(1 , n, 1, st[x], st[y], z); } int get_lca(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]] > dep[top[y]]) swap(x,y); y = fa[top[y]]; } return dep[x] < dep[y] ? x : y; } int calc(int x,int y) { // y -> x int lst=0; while(top[x] != top[y]) { lst = top[y]; y = fa[top[y]]; } if(y == x) return lst; else { return bu[st[x] + 1]; } } int main() { // setIO("input"); scanf("%d%d",&n,&m); for(int i=1;i<n;++i) { int x,y; scanf("%d%d",&x,&y); G[x].pb(y); G[y].pb(x); } for(int i=1;i<=n;++i) { scanf("%d",&val[i]); } scanf("%d",&root); dfs1(root, 0); dfs2(root, root); build(1, n, 1); for(int i=1;i<=m;++i) { int op,x,y,z; scanf("%d",&op); if(op==1) { scanf("%d",&root); } if(op==2) { scanf("%d%d%d",&x,&y,&z); upd(x, y, z); } if(op==3) { scanf("%d",&x); if(x == root) { // 特判 printf("%d\n",mn[1]); continue; } int lca=get_lca(root, x); if(lca != x) { printf("%d\n",query(1,n,1,st[x], ed[x])); } else { int re = inf; int ch = calc(x, root); // [st[x], ed[x]]; if(st[ch] > 1) re = min(re, query(1,n,1,1,st[ch]-1)); if(ed[ch] < n) re = min(re, query(1,n,1,ed[ch]+1,n)); printf("%d\n",re); } } } return 0; }