【BZOJ3306】樹（樹剖換根）（ZKW線段樹）

傳送門

老年選手複習樹剖換根，無題解。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
	static cs int Rlen=1<<22|1;
	static char buf[Rlen],*p1,*p2;
	inline char get_char(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;}
	inline char peek(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1;}
	inline char ga(){while(!isalpha(peek()))++p1;return gc();}
	
	template<typename T>
	inline T get(){
		char c;T num;
		while(!isdigit(c=gc()));num=c^48;
		while(isdigit(c=gc()))num=((num+(num<<2))<<1)+(c^48);
		return num;
	}
	inline int gi(){return get<int>();}
}
using namespace IO;

using std::cerr;
using std::cout;

cs int N=1e5+5;
int n,q;

int last[N],nxt[N],to[N],ecnt;
inline void adde(int u,int v){
	nxt[++ecnt]=last[u],last[u]=ecnt,to[ecnt]=v;
}

int fa[N],d[N],top[N],siz[N],son[N];
int in[N],out[N],pos[N],clk;
void dfs1(int u,int p){
	d[u]=d[p]+1;in[u]=++clk;pos[clk]=u;siz[u]=1;
	for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]]){
		dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;
	}
	out[u]=clk;
}
void dfs2(int u,int tp){
	top[u]=tp;
	for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]])
	dfs2(v,v==son[u]?tp:v);
}
inline int jump(int u,int t){
	int res=0;
	while(top[u]!=top[t]){
		res=top[u];u=fa[res];
	}
	return u==t?res:son[t];
}

int val[N];
namespace SGT{
	int mn[N<<2],M;
	inline void build(){
		for(M=1;M<=n+1;M<<=1);
		for(int re i=M+1;i<=M+n;++i)mn[i]=val[pos[i-M]];
		mn[M]=0x3f3f3f3f;
		for(int re i=M+n+1;i<M+M;++i)mn[i]=0x3f3f3f3f;
		for(int re i=M-1;i;--i)mn[i]=std::min(mn[i<<1],mn[i<<1|1]);
	}
	inline void modify(int p,int v){
		for(mn[p+=M]=v,p>>=1;p;p>>=1)mn[p]=std::min(mn[p<<1],mn[p<<1|1]);
	}
	inline int query(int l,int r){
		int ans=0x3f3f3f3f;
		for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
			if(l&1^1)ans=std::min(ans,mn[l^1]);
			if(r&1)  ans=std::min(ans,mn[r^1]);
		}
		return ans;
	}
}

int rt=1;

signed main(){
#ifdef zxyoi
	freopen("tree.in","r",stdin);
#endif 
	n=gi(),q=gi();
	for(int re i=1;i<=n;++i){
		fa[i]=gi(),val[i]=gi();
		adde(fa[i],i);
	}
	dfs1(1,0);dfs2(1,1);SGT::build();
	while(q--){
		switch(ga()){
			case 'V':{
				int u=gi(),val=gi();
				SGT::modify(in[u],val);
				break;
			}
			case 'E':{rt=gi();break;}
			case 'Q':{
				int u=gi();
				if(u==rt){cout<<SGT::mn[1]<<"\n";}
				else if(in[u]<in[rt]&&in[rt]<=out[u]){
					int v=jump(rt,u);
					cout<<std::min(SGT::query(1,in[v]-1),SGT::query(out[v]+1,n))<<"\n";
				}
				else cout<<SGT::query(in[u],out[u])<<"\n";
				break;
			}
		}
	}
	return 0;
}