@[shangcheng](/user/114153) ~~又臭又长……（我没想歪，您用这样的形容词来形容您的代码，必将受到谴责）~~
by mnesia @ 2020-02-03 16:23:22
整体二分不好吗（
by SSerxhs @ 2020-02-03 16:23:48
@[SSerxhs](/user/29826) 不会啊，我太蒻了
by Saliеri @ 2020-02-03 16:24:26
@[shangcheng](/user/114153)
奆
by gyh20 @ 2020-02-03 16:56:27
@[shangcheng](/user/114153) 太奆了，吊打我
by gyh20 @ 2020-02-03 16:57:06
```
#include <bits/stdc++.h>
using namespace std;
namespace Fread {
const int SIZE = 1 << 23;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
}
namespace Fwrite {
const int SIZE = 1 << 23;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T)
flush();
}
struct NTR {
~NTR() {
flush();
}
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return x * f;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int _ = 1e5 + 10;
int n, m, cnt, len, a[_], b[_];
int tot, head[_], to[_ << 1], nxt[_ << 1];
int lc[_ * 200], rc[_ * 200], sum[_ * 200];
int rt[_], dep[_], fa[_][20], dfc, st[_], ed[_];
int c[2], tmp[2][_];
struct que {
int k, a, b;
} q[_];
inline void add(int u, int v) {
to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
to[++tot] = u, nxt[tot] = head[v], head[v] = tot;
}
void update(int &u, int l, int r, int pos, int val) {
if (!u) u = ++cnt;
sum[u] += val;
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) update(lc[u], l, mid, pos, val);
else update(rc[u], mid + 1, r, pos, val);
}
int query(int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1, s = 0;
for (int i = 1; i <= c[0]; ++i) s += sum[lc[tmp[0][i]]];
for (int i = 1; i <= c[1]; ++i) s -= sum[lc[tmp[1][i]]];
if (k <= s) {
for (int i = 1; i <= c[0]; ++i) tmp[0][i] = lc[tmp[0][i]];
for (int i = 1; i <= c[1]; ++i) tmp[1][i] = lc[tmp[1][i]];
return query(l, mid, k);
} else {
for (int i = 1; i <= c[0]; ++i) tmp[0][i] = rc[tmp[0][i]];
for (int i = 1; i <= c[1]; ++i) tmp[1][i] = rc[tmp[1][i]];
return query(mid + 1, r, k - s);
}
}
void dfs(int x) {
for (int i = 1; i < 20; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
dep[x] = dep[fa[x][0]] + 1, st[x] = ++dfc;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa[x][0]) continue;
fa[v][0] = x;
dfs(v);
}
ed[x] = dfc;
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int t = dep[x] - dep[y];
for (int i = 0; i < 20; ++i)
if (t & (1 << i)) x = fa[x][i];
if (x == y) return x;
for (int i = 19; ~i; --i)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
inline int lowbit(int x) {
return x & (-x);
}
inline void change(int pos, int val, int op) {
for (; pos <= n; pos += lowbit(pos)) update(rt[pos], 1, len, val, op);
}
signed main() {
n = read(), m = read(), len = n;
for (int i = 1; i <= n; ++i) a[i] = b[i] = read();
for (int i = 1; i < n; ++i) add(read(), read());
for (int i = 1; i <= m; ++i) {
q[i].k = read(), q[i].a = read(), q[i].b = read();
if (!q[i].k) b[++len] = q[i].b;
}
sort(b + 1, b + len + 1), len = unique(b + 1, b + len + 1) - b - 1;
for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
dfs(1);
for (int i = 1; i <= n; ++i) change(st[i], a[i], 1), change(ed[i] + 1, a[i], -1);
for (int i = 1; i <= m; ++i) {
int x = q[i].a, y = q[i].b, k = q[i].k, lca, flca, s;
if (k) {
lca = LCA(x, y), flca = fa[lca][0], c[0] = c[1] = 0;
s = dep[x] + dep[y] - dep[lca] - dep[flca];
if (k > s) {
printf("invalid request!\n");
continue;
}
for (int i = st[x]; i; i -= lowbit(i)) tmp[0][++c[0]] = rt[i];
for (int i = st[y]; i; i -= lowbit(i)) tmp[0][++c[0]] = rt[i];
for (int i = st[lca]; i; i -= lowbit(i)) tmp[1][++c[1]] = rt[i];
for (int i = st[flca]; i; i -= lowbit(i)) tmp[1][++c[1]] = rt[i];
printf("%d\n", b[query(1, len, s - k + 1)]);
} else {
change(st[x], a[x], -1), change(ed[x] + 1, a[x], 1);
a[x] = lower_bound(b + 1, b + len + 1, y) - b;
change(st[x], a[x], 1), change(ed[x] + 1, a[x], -1);
}
}
return 0;
}
```
by whoshishen @ 2022-12-12 18:05:11