1 /**************************************************************  2     Problem: 3306  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:1644 ms  7     Memory:22996 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int N = 100005; 15 const int M = 400005; 16 const int inf = 1e9; 17   18 struct edge { 19     int next, to; 20     edge() {} 21     edge(int _n, int _t) : next(_n), to(_t) {} 22 } e[N]; 23   24 int cnt_edge, first[N]; 25   26 struct tree_node { 27     int v, dep, st, ed, fa[17]; 28 } tr[N]; 29   30 struct seg_node { 31     seg_node *lson, *rson; 32     int l, r, mn; 33 } *seg_rt, mempool[M], *cnt_seg = mempool; 34   35 int n, root; 36 int q[N], cnt_seq; 37   38 inline int read() { 39     int x = 0, sgn = 1; 40     char ch = getchar(); 41     while (ch < ‘0‘ || ‘9‘ < ch) { 42         if (ch == ‘-‘) sgn = -1; 43         ch = getchar(); 44     } 45     while (‘0‘ <= ch && ch <= ‘9‘) { 46         x = x * 10 + ch - ‘0‘; 47         ch = getchar(); 48     } 49     return sgn * x; 50 } 51   52 inline void add_edge(int x, int y) { 53     e[++cnt_edge] = edge(first[x], y); 54     first[x] = cnt_edge; 55 } 56   57 void dfs(int p) { 58     int x; 59     q[tr[p].st = ++cnt_seq] = p; 60     for (x = 1; x <= 16; ++x) 61         tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1]; 62     for (x = first[p]; x; x = e[x].next) { 63         tr[e[x].to].dep = tr[p].dep + 1; 64         dfs(e[x].to); 65     } 66     tr[p].ed = cnt_seq; 67 } 68   69 #define Lson p -> lson 70 #define Rson p -> rson 71 #define Mn p -> mn 72 #define L p -> l 73 #define R p -> r 74 #define mid (L + R >> 1) 75 inline void seg_update(seg_node *p) { 76     Mn = min(Lson -> mn, Rson -> mn); 77 } 78   79 void seg_build(seg_node *&p, int l, int r) { 80     p = ++cnt_seg, L = l, R = r; 81     if (l == r) { 82         Mn = tr[q[l]].v; 83         return; 84     } 85     seg_build(Lson, l, mid), seg_build(Rson, mid + 1, r); 86     seg_update(p); 87 } 88   89 void seg_modify(seg_node *p, int pos, int v) { 90     if (L == R) { 91         Mn = v; 92         return; 93     } 94     if (pos <= mid) seg_modify(Lson, pos, v); 95     else seg_modify(Rson, pos, v); 96     seg_update(p); 97 } 98   99 int seg_query(seg_node *p, int l, int r) {100     if (l > r) return inf;101     if (L == l && r == R) return Mn;102     if (r <= mid) return seg_query(Lson, l, r);103     else if (mid < l) return seg_query(Rson, l, r);104     else return min(seg_query(Lson, l, mid), seg_query(Rson, mid + 1, r));105 }106  107 int main() {108     int i, Q, now, x, v;109     char st[10];110     n = read(), Q = read();111     for (i = 1; i <= n; ++i) {112         tr[i].fa[0] = read(), tr[i].v = read();113         if (tr[i].fa[0]) add_edge(tr[i].fa[0], i);114     }115     tr[root = 1].dep = 1;116     dfs(1);117     seg_build(seg_rt, 1, n);118     while (Q--) {119         scanf("%s", st + 1), x = read();120         if (st[1] == ‘V‘)121             seg_modify(seg_rt, tr[x].st, read());122         else if (st[1] == ‘E‘) root = x;123         else {124             if (root == x) printf("%d\n", seg_rt -> mn); else125             if (tr[x].st <= tr[root].st && tr[root].ed <= tr[x].ed) {126                 for (i = 16, now = root; ~i; --i)127                     if (tr[tr[now].fa[i]].dep > tr[x].dep) now = tr[now].fa[i];128                 printf("%d\n", min(seg_query(seg_rt, 1, tr[now].st - 1), seg_query(seg_rt, tr[now].ed + 1, n)));129             } else130             printf("%d\n", seg_query(seg_rt, tr[x].st, tr[x].ed));131         }132     }133     return 0;134 }