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
123
| #include <bits/stdc++.h>
using namespace std;
#define id(x) (lower_bound(b + 1, b + L + 1, x) - b)
#define rid(x) (b[x])
#define lson(x) (node[x].l)
#define rson(x) (node[x].r)
#define sum(x) (node[x].sum)
#define lowbit(x) (x & (-x))
const int MAXN = 80005 * 2;
vector<int> G[MAXN];
struct opt {int k, a, b;} op[MAXN];
struct Node {
int l, r, sum;
Node() {l = r = sum = 0;}
} node[MAXN * 80];
int c[MAXN], cnt;
int N, Q, L;
int t[MAXN], b[MAXN];
int q1[MAXN], q2[MAXN], len1, len2;
int dep[MAXN], dfn[MAXN], f[MAXN], son[MAXN], top[MAXN], size[MAXN], dfn_idx;
void insert(int& u, int l, int r, int p, int val) {
if (u == 0) u = ++cnt;
sum(u) += val;
if (l == r) return;
int mid = (l + r) >> 1;
if (p <= mid) insert(lson(u), l, mid, p, val);
else insert(rson(u), mid + 1, r, p, val);
}
void modify(int u, int p, int val) {
for (; u <= N; u += lowbit(u)) insert(c[u], 1, L, p, val);
}
void dfs1(int u, int fa) {
dep[u] = dep[fa] + 1;
f[u] = fa;
size[u] = 1;
for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
int v = *it;
if (v == fa) continue;
dfs1(v, u);
if (size[v] > size[son[u]]) son[u] = v;
size[u] += size[v];
}
}
void dfs2(int u, int topc) {
dfn[u] = ++dfn_idx;
top[u] = topc;
modify(dfn[u], t[u], 1);
if (son[u]) dfs2(son[u], topc);
for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
int v = *it;
if (v == son[u] || v == f[u]) continue;
dfs2(v, v);
}
}
void pre_bin(int u, int* a, int& len) {
for (; u >= 1; u -= lowbit(u)) a[++len] = c[u];
}
int pre(int u, int v) {
len1 = len2 = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
pre_bin(dfn[u], q1, len1);
pre_bin(dfn[top[u]] - 1, q2, len2);
u = f[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
pre_bin(dfn[u], q1, len1);
pre_bin(dfn[v] - 1, q2, len2);
return v;
}
int query(int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1, rsum = 0;
for (int i = 1; i <= len1; ++i) rsum += sum(rson(q1[i]));
for (int i = 1; i <= len2; ++i) rsum -= sum(rson(q2[i]));
if (k <= rsum) {
for (int i = 1; i <= len1; ++i) q1[i] = rson(q1[i]);
for (int i = 1; i <= len2; ++i) q2[i] = rson(q2[i]);
return query(mid + 1, r, k);
}
else {
for (int i = 1; i <= len1; ++i) q1[i] = lson(q1[i]);
for (int i = 1; i <= len2; ++i) q2[i] = lson(q2[i]);
return query(l, mid, k - rsum);
}
}
int main() {
scanf("%d%d", &N, &Q);
for (register int i = 1; i <= N; ++i) scanf("%d", &t[i]), b[++L] = t[i], c[i] = ++cnt;
for (register int i = 1; i < N; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
for (register int i = 1; i <= Q; ++i) {
scanf("%d%d%d", &op[i].k, &op[i].a, &op[i].b);
if (op[i].k == 0) b[++L] = op[i].b;
}
sort(b + 1, b + L + 1);
L = unique(b + 1, b + L + 1) - b - 1;
for (register int i = 1; i <= N; ++i) t[i] = id(t[i]);
dfs1(1, 0);
dfs2(1, 1);
for (register int i = 1; i <= Q; ++i) {
int k = op[i].k, a = op[i].a, b_ = op[i].b;
if (k == 0) {
b_ = id(b_);
modify(dfn[a], t[a], -1);
t[a] = b_;
modify(dfn[a], t[a], 1);
}
else {
int lca = pre(a, b_);
int maxk = dep[a] + dep[b_] - dep[lca] * 2 + 1;
if (maxk < k) {
puts("invalid request!");
continue;
}
printf("%d\n", rid(query(1, L, k)));
}
}
return 0;
}
|