学步园

题目大意就是给你一棵树，支持换根、修改点权、求一个点的子树的最小值。

对于这道题，如果没有换根操作，就直接上RMQ。

然而有了换根，我们可以先以1号点为根处理出这棵树的dfs序用线段树来维护一段dfs序的最小值，修改点权就不说了。

对于每个查询

设查询的点X；

设此时根为R；

设L[X]代表X在dfs序中第一次出现的位置

设R[X]代表X在dfs序中第一次出现的位置

如图的一棵树

1：当X等于R时 比如X=R=1

直接输出整棵树的最小值。

2：当R不在X的子树中 比如X=2 R=3

明显就是X的子树中的最小值

即为L[X]到R[X]的最小值

3：当X是R的祖先时

首先确定包含点的范围：

举两个例子：当X=2、R=4时是1、2、3、5
， 当X=1、R=4时是1、3。

通过这两个例子，我们可以看出包含的范围就是整棵树除去E所在的子树（E是X的儿子，也是R的祖先）。

那么答案就是L[1]到L[E]-1与R[E]+1到R[1]的最小值

（这一点要仔细想想，当初也是花了好久才弄懂）

最后说一下几个要注意的地方吧

求dfs序，不能直接dfs，会爆栈，所以。。。。手动栈吧

找E的时候不能一步一步往上跳，用倍增吧

Ps:其实上面两点都不要管就可以过原始数据，只是我们oj丧心病狂处处卡人啊。。。。

附代码

#include<cstdio>
#include<iostream>
#include<cmath>
const double eps=0.0000001;
const int maxn=100010*2,maxm=maxn*8;
using namespace std;
int tot=0;
int pre[maxn],son[maxn];
int now[maxn];
void add(int a,int b){
	pre[++tot]=now[a];
	now[a]=tot;
	son[tot]=b;
}

inline int read(){
    char ch=getchar(); int tmp=0;
    while (ch<'0' || ch>'9') ch=getchar();
    for (;ch<='9' && ch>='0';ch=getchar()) tmp=tmp*10+ch-'0';
    return tmp;
}
int n,m;
int a[maxn];
void init(){
	n=read();
	m=read();
	for (int i=1;i<=n;++i){
		int a=read();
		int b=read();
		add(a,i);
		::a[i]=b;
	}
}
int l[maxn],r[maxn];
int dep[maxn];
int sum=0;
int maxdep=0;
int fa[maxn][40];
int num[maxn];
int syssta[maxn];
int bre[maxn];
void dfs(){
	int tot=0;
	syssta[++tot]=1;
	dep[1]=1;
	for (int i=1;i<=n;++i)
		bre[i]=now[i];
	while (tot){
		if (bre[syssta[tot]]==now[syssta[tot]]){
			l[syssta[tot]]=++sum;
			num[sum]=a[syssta[tot]];
		}
		if (!bre[syssta[tot]]){
			r[syssta[tot]]=++sum;
			num[sum]=a[syssta[tot]];
			tot--;
		}
		else {
			syssta[tot+1]=son[bre[syssta[tot]]];
			fa[son[bre[syssta[tot]]]][0]=syssta[tot];
			bre[syssta[tot]]=pre[bre[syssta[tot]]];
			dep[syssta[tot+1]]=dep[syssta[tot]]+1;
			maxdep=max(maxdep,dep[syssta[tot+1]]);
			tot++;
		}
	}
}

void prepare(){
	int quit=(int)(log(maxdep)/log(2)+eps);
	for (int i=1;i<=quit;++i)
		for (int j=1;j<=n;++j)
			fa[j][i]=fa[fa[j][i-1]][i-1];
}

inline int find(int x,int root){
	swap(x,root);
	int gap=dep[x]-dep[root]-1;
	while (gap){
		int tmp=(int)(log(gap)/log(2)+eps);
		x=fa[x][tmp];
		gap-=1<<tmp;
	}
	return x;
}
int tree[maxm];
void inline updata(int p){
	int Ls=p*2,Rs=Ls+1;
	tree[p]=tree[Ls]<tree[Rs]?tree[Ls]:tree[Rs];
}
int wh[maxn];
void build(int p,int l,int r){
	if (l==r){
		tree[p]=num[l];
		wh[l]=p;
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	updata(p);
}

void ins(int p,int add){
	tree[p]=add;
	p=p>>1;
	while (p){
		updata(p);
		p=p>>1;
	}
}
inline int min(int a,int b){
	return a<b?a:b;
}
int countit(int p,int l,int r,int fir,int las){
	if (l==fir && r==las)
		return tree[p];
	int mid=(l+r)/2;
	int Ls=p*2,Rs=Ls+1;
	if (las<=mid) return countit(Ls,l,mid,fir,las);
	if (fir>mid) return countit(Rs,mid+1,r,fir,las);
	int ans=countit(Ls,l,mid,fir,mid);
	ans=min(ans,countit(Rs,mid+1,r,mid+1,las));
	return ans;
}

void work(){
	dep[1]=1;
	dfs();
	prepare();
	n*=2;
	build(1,1,n);
	int root=1;
	while (m--){
		char tmp[3];
		scanf("%s",tmp);
		if (tmp[0]=='V'){
			int a=read();
			int b=read();
			ins(wh[l[a]],b);
			ins(wh[r[a]],b);
		}
		if (tmp[0]=='E')
			root=read();
		if (tmp[0]=='Q'){
			int x=read();
			int ans;
			if (x==root) ans=tree[1];
			else
			if (l[x]>l[root] || r[x]<r[root]) 
				ans=countit(1,1,n,l[x],r[x]);
			else{
				int xx=find(x,root);
				ans=min(countit(1,1,n,1,l[xx]-1),countit(1,1,n,r[xx]+1,n));
			}
			printf("%d\n",ans);
		}
	}
}

int main(){
	init();
	work();
	return 0;
}