【題解】
這道題除去根操作就是普通的樹鍊剖分了。但是有換根操作怎麼處理呢？
我們可以發現如果現在的根不在查詢的點的子樹裡，那麼對本次查詢沒有影響。如果現在的跟在查詢的點x的子樹裡，那麼答案将變為整棵樹除去現在的根root所屬的x的孩子的子樹。
為了快速确定root屬于x的哪一個孩子，我們可以寫個倍增。
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 #include<cmath>
5 #define N 200010
6 #define LL long long
7 #define rg register
8 #define ls (u<<1)
9 #define rs (u<<1|1)
10 #define mid ((a[u].l+a[u].r)>>1)
11 using namespace std;
12 int n,m,tot,cnt,root=1,last[N],dep[N],siz[N],top[N],fa[N],hvy[N],dfn[N],pos[N],v[N],p[N][20];
13 struct edge{
14 int to,pre;
15 }e[N<<1];
16 struct tree{
17 int l,r,mn,num; bool mark;
18 }a[N<<2];
19 inline int read(){
20 int k=0,f=1; char c=getchar();
21 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
22 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
23 return k*f;
24 }
25 void find(int u,int f){
26 p[u][0]=f;
27 for (int i=1;i<=log2(dep[u]);i++) p[u][i]=p[p[u][i-1]][i-1];
28 for (int i=last[u],to=e[i].to;i;i=e[i].pre,to=e[i].to)
29 if(to!=f) find(to,u);
30 }
31 void dfs1(int x){
32 siz[x]=1; dep[x]=dep[fa[x]]+1;
33 for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=fa[x]){
34 fa[to]=x; dfs1(to); siz[x]+=siz[to];
35 if(siz[x]>siz[hvy[x]]) hvy[x]=to;
36 }
37 }
38 void dfs2(int x,int tp){
39 top[x]=tp; dfn[x]=++cnt; pos[cnt]=x;
40 if(hvy[x]) dfs2(hvy[x],tp);
41 for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=fa[x]&&to!=hvy[x])
42 dfs2(to,to);
43 }
44 void build(int u,int l,int r){
45 a[u].l=l; a[u].r=r;
46 if(l<r) build(ls,l,mid),build(rs,mid+1,r),a[u].mn=min(a[ls].mn,a[rs].mn);
47 else a[u].mn=v[pos[l]];
48 }
49 inline void pushdown(int u){
50 a[u].mark=0; a[ls].mark=a[rs].mark=1;
51 a[ls].num=a[rs].num=a[u].num;
52 a[ls].mn=a[rs].mn=a[u].mn;
53 }
54 void update(int u,int l,int r,int d){
55 if(l<=a[u].l&&a[u].r<=r){
56 a[u].mark=1; a[u].num=d; a[u].mn=d;
57 return;
58 }
59 if(a[u].mark) pushdown(u);
60 if(l<=mid) update(ls,l,r,d);
61 if(r>mid) update(rs,l,r,d);
62 a[u].mn=min(a[ls].mn,a[rs].mn);
63 }
64 int query(int u,int l,int r){
65 if(l<=a[u].l&&a[u].r<=r) return a[u].mn;
66 if(a[u].mark) pushdown(u); int ret=2e9;
67 if(l<=mid) ret=min(ret,query(ls,l,r));
68 if(r>mid) ret=min(ret,query(rs,l,r));
69 return ret;
70 }
71 int main(){
72 n=read(); m=read();
73 for(rg int i=1;i<n;i++){
74 int u=read(),v=read();
75 e[++tot]=(edge){v,last[u]}; last[u]=tot;
76 e[++tot]=(edge){u,last[v]}; last[v]=tot;
77 }
78 for(rg int i=1;i<=n;i++) v[i]=read();
79 root=read();
80 dfs1(root); dfs2(root,root); build(1,1,n); find(root,0);
81 while(m--){
82 int opt=read();
83 if(opt==1) root=read();
84 else if(opt==2){
85 int x=read(),y=read(),d=read(),t1=top[x],t2=top[y];
86 while(t1!=t2){
87 if(dep[t1]<dep[t2]) swap(t1,t2),swap(x,y);
88 update(1,dfn[t1],dfn[x],d);
89 x=fa[t1]; t1=top[x];
90 }
91 if(dep[x]>dep[y]) swap(x,y);
92 update(1,dfn[x],dfn[y],d);
93 }
94 else if(opt==3){
95 int x=read();
96 if(dfn[x]<dfn[root]&&dfn[root]<=dfn[x]+siz[x]-1){
97 int y=root;
98 for(int i=log2(dep[y]-dep[x]);i>=0&&(dep[x]+1)!=dep[y];i--)
99 if(dep[p[y][i]]>=dep[x]+1) y=p[y][i];
100 int ans=2e9;
101 ans=min(ans,query(1,1,dfn[y]-1));
102 ans=min(ans,query(1,dfn[y]+siz[y],n));
103 printf("%d
",ans);
104 }
105 else{
106 if(x==root) printf("%d
",query(1,1,n));
107 else printf("%d
",query(1,dfn[x],dfn[x]+siz[x]-1));
108 }
109 }
110 }
111 return 0;
112 } View Code