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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int N = 2e5 + 66;
int ver[N << 1], nex[N << 1], head[N], cnt;
inline void add_edge(int x, int y)
{
ver[++ cnt] = y;
nex[cnt] = head[x];
return (void)(head[x] = cnt);
}
int n, m, tot, a[N];
int dfn[N], siz[N], fa[N], vis[N];
struct SEGMENTTREE
{
int maxv, tag;
}tree[N << 2];
inline void dfs(int x, int yhm_fa)
{
dfn[x] = ++ tot, siz[x] = 1;
int i, y;
for (i = head[x]; i; i = nex[i])
{
y = ver[i];
if (y == yhm_fa) continue;
fa[y] = x;
dfs(y, x);
siz[x] += siz[y];
}
return;
}
inline void up(int p)
{
int l = p << 1, r = (p << 1) | 1;
return (void)(tree[p].maxv = max(tree[l].maxv, tree[r].maxv));
}
inline void down(int p)
{
if (! tree[p].tag) return;
int l = p << 1, r = (p << 1) | 1, c = tree[p].tag;
tree[l].maxv = max(tree[l].maxv, c), tree[l].tag = max(tree[l].tag, c),
tree[r].maxv = max(tree[r].maxv, c), tree[r].tag = max(tree[r].tag, c);
return (void)(tree[p].tag = 0);
}
inline void build(int p, int l, int r)
{
tree[p].maxv = -1;
if (l == r) return;
int mid = (l + r) >> 1;
build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
return (void)(up(p));
}
inline void updata(int p, int l, int r, int nl, int nr, int c)
{
if (nl <= l && nr >= r)
{
tree[p].maxv = max(tree[p].maxv, c);
tree[p].tag = max(tree[p].tag, c);
return;
}
down(p);
int mid = (l + r) >> 1;
if (nl <= mid) updata(p << 1, l, mid, nl, nr, c);
if (nr > mid) updata((p << 1) | 1, mid + 1, r, nl, nr, c);
return (void)(up(p));
}
inline int query(int p, int l, int r, int x)
{
if (l == r) return tree[p].maxv;
down(p);
int mid = (l + r) >> 1;
if (x <= mid) return query(p << 1, l, mid, x);
return query((p << 1) | 1, mid + 1, r, x);
}
inline void work(int x, int son)
{
if (vis[son]) return;
updata(1, 1, n, dfn[x], dfn[x], a[x]);
updata(1, 1, n, dfn[x], dfn[son] - 1, a[x]);
updata(1, 1, n, dfn[son] + siz[son], dfn[x] + siz[x] - 1, a[x]);
return (void)(work(fa[x], x), vis[x] = 1);
}
signed main()
{
int i, x, y;
n = read(), m = read();
for (i = 1; i <= n; ++ i) a[i] = read();
for (i = 1; i < n; ++ i)
{
x = read(), y = read();
add_edge(x, y), add_edge(y, x);
}
dfs(1, 0), build(1, 1, n);
while (m --)
{
char sb[66];
cin >> (sb + 1); x = read();
if (sb[1] == 'Q') put(query(1, 1, n, dfn[x]));
else
{
work(fa[x], x); vis[x] = 1;
updata(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, a[x]);
}
}
return 0;
}
|