题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3306
刚开始的时候拿这道题去用LCT维护链翻转，然后splay维护DFS序列，结果敲了10K代码之后果断WA。。。然后实在不想写了，乖乖分类吧：
1.查询的子树根是根
2.根在查询的字树上
3.根不在查询的子树上
然后按照情况求DFS序上的RMQ即可。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define MAXN 200010
#define MAXB 30
#define inf 0x7fffffff
struct edge{
edge *next ;
int t ;
}*head[ MAXN ];
void AddEdge(int s ,int t ){
edge *p =new( edge );
p -> t = t , p -> next = head[ s ];
head[ s ]= p ;
}
int up[ MAXN ][ MAXB ], va[ MAXN ], n , m , h[ MAXN ], first[ MAXN ], last[ MAXN ], arr[ MAXN *2], Index =0, b =0;
void dfs(int v ){
arr[ first[ v ]=++ Index ]= va[ v ];
for( edge *p = head[ v ]; p ; p = p -> next ){
h[ p -> t ]= h[ v ]+1;dfs( p -> t );
}
arr[ last[ v ]=++ Index ]= va[ v ];
}
struct Sgt{
int Min[ MAXN *5], N ;
void Init(int _N ,int*a ){
N =1<<(int(log2( _N ))+1);
for(int i =0; i ++< _N ;) Min[ N + i ]= a[ i ];
for(int i = N -1; i ; i --) Min[ i ]=min( Min[ i <<1], Min[( i <<1)^1]);
}
void Change(int x ,int y ){
Min[ N + x ]= y ;
for(int i =( N + x )>>1; i ; i >>=1) Min[ i ]=min( Min[ i <<1], Min[( i <<1)^1]);
}
int Query(int l ,int r ){
if( l > r )return inf ;
int rec = inf ;
for(int i = N + l -1, j = N + r +1;( i ^ j )!=1; i >>=1, j >>=1){
if(!( i &1)) rec =min( rec , Min[ i ^1]);
if( j &1) rec =min( rec , Min[ j ^1]);
}
return rec ;
}
} sgt ;
int main( ){
scanf("%d%d",&n ,&m );
memset( head ,0,sizeof( head ));
for(int i =0; i ++< n ;){
scanf("%d%d",&up[ i ][0],&va[ i ]);
if( up[ i ][0])AddEdge( up[ i ][0], i );
}
h[1]=0;dfs(1);
b =int(log2( n ))+1;
for(int i =0; i ++< b ;)for(int j =0; j ++< n ;) up[ j ][ i ]= up[ up[ j ][ i -1]][ i -1];
sgt.Init( Index , arr );
char st[1];
int x , y , roof =1;
while( m --){
scanf("%s",&st );
if( st[0]=='V'){
scanf("%d%d",&x ,&y );
sgt.Change( first[ x ], y ), sgt.Change( last[ x ], y );
}else if( st[0]=='E'){
scanf("%d",&roof );
}else{
scanf("%d",&x );
if( h[ x ]== h[ roof ]){
if( x == roof )printf("%d\n", sgt.Query(1, Index ))
;else printf("%d\n", sgt.Query( first[ x ], last[ x ]));
}else{
if( h[ roof ]< h[ x ])printf("%d\n", sgt.Query( first[ x ], last[ x ]))
;else{
int j = roof ;
for(int i = b ; i >=0&& h[ j ]> h[ x ]+1; i --){
if( h[ up[ j ][ i ]]> h[ x ]) j = up[ j ][ i ];
}
if( up[ j ][0]== x )printf("%d\n",min( sgt.Query(1, first[ j ]-1), sgt.Query( last[ j ]+1, Index )));else printf("%d\n", sgt.Query( first[ x ], last[ x ]));
}
}
}
}
return 0;
}
