NO IMAGE

Description


給你一棵大小為n的有根樹,每個點有點權,要求完成以下操作:
V x y把點x的權值變成y
E x把有根樹的根變為x
Q x查詢點x的子樹的最小值

Input


第一行兩個整數n,m,表示點數和運算元。
接下來n行,每行兩個數f,v,第i行的兩個數表示i的父親和i的權值,且保證f接下來m行,每行表示一個操作。

Output


對於每個Q操作,輸出一個整數表示最小值。

Hint


對於30%的資料,n<=1000.
對於100%的資料,n,m<=100000,權值<=10^9

Source


BY BPM

Solution


不考慮修改點權和修改根是很好做的,dfs一輪就可以了。

考慮修改和查詢,我們可以通過dfs把樹轉換成序列,修改、查詢的操作就變成序列上的操作了,線段樹搞定。

再考慮換根。我們讓1恆為根,不難發現如果詢問節點x在當前根root的子樹內,則x在當前根下的子樹仍為x在1位根下的子樹;否則,簡單畫一下圖就可以發現,x在當前根下的子樹變成了除了以1為根時x的子樹外的其餘部分,也就是說把dfs序去掉x以1為根時的子樹那部分後,其餘部分就是x在當前根下的子樹。
繼續用線段樹來做即可。

Code


#include <stdio.h>
#define rep(i, st, ed) for (int i = st; i <= ed; i  = 1)
#define erg(i, st) for (int i = ls[st]; i; i = e[i].next)
#define min(x, y) (x)<(y)?(x):(y)
#define max(x, y) (x)>(y)?(x):(y)
#define INF 0x3f3f3f3f
#define N 100001
#define E N
struct edge{int x, y, next;}e[E];
struct treeNode{
int l, r, mn;
bool operator <(treeNode b){return (l >= b.l)&&(r < b.r)||(l > b.l)&&(r <= b.r);}
bool operator <=(treeNode b){return (l >= b.l)&&(r <= b.r);}
}t[N << 2 | 1], rc[N];
int father[N], ls[N], v[N];
int edgeCnt = 0, rCnt = 0;
inline int read(){
int x = 0; char ch = getchar();
while (ch < '0' || ch > '9'){ch = getchar();}
while (ch <= '9' && ch >= '0'){x = (x << 1)   (x << 3)   ch - '0'; ch = getchar();}
return x;
}
inline void addEdge(int x, int y){
e[   edgeCnt] = (edge){x, y, ls[x]}; ls[x] = edgeCnt;
}
inline void modify(int now, int x, int v){
if (t[now].l == t[now].r){
t[now].mn = v;
return;
}
int mid = (t[now].l   t[now].r) >> 1;
if (x <= mid){modify(now << 1, x, v);}
if (x > mid){modify(now << 1 | 1, x, v);}
t[now].mn = min(t[now << 1].mn, t[now << 1 | 1].mn);
}
inline int query(int now, int l, int r){
if (l > r){return INF;}
if (t[now].l == l && t[now].r == r){return t[now].mn;}
int mid = (t[now].l   t[now].r) >> 1;
if (r <= mid){return query(now << 1, l, r);}
if (l > mid){return query(now << 1 | 1, l, r);}
return min(query(now << 1, l, mid), query(now << 1 | 1, mid   1, r));
}
inline void build(int now, int l, int r){
t[now] = (treeNode){l, r, 0};
if (l == r){return ;}
int mid = (l   r) >> 1;
build(now << 1, l, mid);
build(now << 1 | 1, mid   1, r);
}
inline void dfs(int fa, int now){
rc[now].mn = rc[now].l = rc[now].r =    rCnt;
modify(1, rc[now].l, v[now]);
erg(i, now){
dfs(now, e[i].y);
rc[now].r = max(rc[now].r, rc[e[i].y].r);
}
}
int main(void){
int n = read(), m = read();
rep(i, 1, n){
father[i] = read(); v[i] = read();
addEdge(father[i], i);
}
build(1, 1, n);
int root = 1;
dfs(0, root);
rep(i, 1, m){
char ch = getchar();
int x = read();
if (ch == 'V'){
int y = read();
modify(1, rc[x].l, y);
}else if (ch == 'Q'){
if (x == root){
printf("%d\n", query(1, 1, rCnt));
}else if (rc[root] < rc[x]){
int now;
erg(i, x){
if (rc[root] <= rc[e[i].y]){
now = e[i].y;
break;
}
}
printf("%d\n", min(query(1, 1, rc[now].l - 1), query(1, rc[now].r   1, rCnt)));
}else{
printf("%d\n", query(1, rc[x].l, rc[x].r));
}
}else if (ch == 'E'){
root = x;
}
}
return 0;
}