1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include <cstdio>
#include <cmath>
#include <vector>
inline int min(const int x, const int y) {return x < y ? x : y;}
int fa[100005][20], Dep[100005], In[100005], Out[100005], val[100005], n, cnt;
std::vector<int> sons[100005];
struct Segment_tree {
struct Node {
int l, r, v;
} c[400005];
void make_tree(const int O, const int L, const int R) {
c[O].l = L, c[O].r = R;
if (L != R) make_tree(O << 1, L, L + R >> 1), make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
}
void update(const int O, const int p, const int x) {
if (c[O].l == c[O].r) {c[O].v = x; return;}
if (p <= c[O << 1].r) update(O << 1, p, x);
else update(O << 1 | 1, p, x);
c[O].v = min(c[O << 1].v, c[O << 1 | 1].v);
}
int query(const int O, const int l, const int r) const {
if (l > r) return 0x3fffffff;
if (l <= c[O].l && c[O].r <= r) return c[O].v;
const int mid(c[O << 1].r);
int ans(0x3fffffff);
if (l <= mid) ans = min(ans, query(O << 1, l, r));
if (mid < r) ans = min(ans, query(O << 1 | 1, l, r));
return ans;
}
} Tree;
inline void dfs(int u) {
Tree.update(1, In[u] = ++ cnt, val[u]);
int MAX(ceil(log2(Dep[u] = Dep[fa[u][0]] + 1)));
for (int i(1); i <= MAX; ++ i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (auto i : sons[u]) if (i != fa[u][0]) dfs(i);
Out[u] = cnt;
}
inline int LCA(int x, int y) {
if (Dep[x] < Dep[y]) {int t(x); x = y, y = t;}
int MAX(ceil(log2(n)));
for (int i(0); i <= MAX; ++ i) if (Dep[x] - Dep[y] & 1 << i) x = fa[x][i];
if (x == y) return x;
for (int i(MAX); i >= 0; -- i)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
inline int Jump(int x, const int y) {
int MAX(ceil(log2(n)));
for (int i(0); i <= MAX; ++ i) if (Dep[x] - Dep[y] - 1 & 1 << i) x = fa[x][i];
return x;
}
int main() {
int m, root(1);
scanf("%d%d", &n, &m);
Tree.make_tree(1, 1, n);
for (int i(1); i <= n; ++ i) {
scanf("%d%d", &fa[i][0], val + i);
if (fa[i][0]) sons[fa[i][0]].push_back(i);
}
dfs(1);
while (m --) {
char op;
int x;
scanf(" %c%d", &op, &x);
if (op == 'V') {
int y;
scanf("%d", &y);
Tree.update(1, In[x], y);
} else if (op == 'E') root = x;
else {
if (x == root) {printf("%d\n", Tree.query(1, 1, n)); continue;}
const int lca(LCA(x, root));
if (lca != x) printf("%d\n", Tree.query(1, In[x], Out[x]));
else {
int y(Jump(root, x));
printf("%d\n", min(Tree.query(1, 1, In[y] - 1), Tree.query(1, Out[y] + 1, n)));
}
}
}
return 0;
}
|