```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <cmath>
#include <functional>
template <typename T> inline void read(T& t) {
int f = 0, c = getchar(); t = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
if (f) t = -t;
}
#if __cplusplus >= 201103L
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
read(t); read(args...);
}
#else
template <typename T1, typename T2>
inline void read(T1& t1, T2& t2) { read(t1); read(t2); }
template <typename T1, typename T2, typename T3>
inline void read(T1& t1, T2& t2, T3& t3) { read(t1, t2); read(t3); }
template <typename T1, typename T2, typename T3, typename T4>
inline void read(T1& t1, T2& t2, T3& t3, T4& t4) { read(t1, t2, t3); read(t4); }
template <typename T1, typename T2, typename T3, typename T4, typename T5>
inline void read(T1& t1, T2& t2, T3& t3, T4& t4, T5& t5) { read(t1, t2, t3, t4); read(t5); }
#endif // C++11
template <typename T> inline bool chkMin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkMax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
#ifdef WIN32
#define LLIO "%I64d"
#else
#define LLIO "%lld"
#endif // WIN32 long long
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (A); I >= (B); --I)
#define erep(I, X) for (int I = head[X]; I; I = next[I])
const int maxn = 8e4 + 207;
int v[maxn << 1], head[maxn], next[maxn << 1], a[maxn];
int dep[maxn], son[maxn], top[maxn], size[maxn], fa[maxn], dfn[maxn], b[maxn];
int n, m, etot, xys;
inline void ae(int x, int y) {
v[++etot] = y; next[etot] = head[x]; head[x] = etot;
v[++etot] = x; next[etot] = head[y]; head[y] = etot;
}
void dfs(int x) {
size[x] = 1; dep[x] = dep[fa[x]] + 1;
erep(i, x) if (v[i] ^ fa[x]) {
fa[v[i]] = x;
dfs(v[i]);
size[x] += size[v[i]];
if (size[v[i]] > size[son[x]]) son[x] = v[i];
}
}
void dfs(int x, int t) {
top[x] = t; dfn[x] = ++xys; b[xys] = a[x];
if (son[x]) dfs(son[x], t);
erep(i, x) if (v[i] ^ fa[x] && v[i] ^ son[x])
dfs(v[i], v[i]);
}
int sum[maxn << 8], left[maxn << 8], right[maxn << 8];
int tot, all, logall, logn;
void insert(int &curr, int l, int r, int pos, int val) {
if (!curr) curr = ++tot;
sum[curr] += val;
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) insert(left[curr], l, mid, pos, val);
else insert(right[curr], mid + 1, r, pos, val);
}
int querySum(int curr, int lb, int rb, int l, int r) {
if (!curr || l > rb || r < lb) return 0;
if (l <= lb && r >= rb) return sum[curr];
int mid = (lb + rb) >> 1;
return querySum(left[curr], lb, mid, l, r) + querySum(right[curr], mid + 1, rb, l, r);
}
int root[maxn];
inline int greaterBit(int l, int r, int x) {
int ret = 0;
for (; r; r -= r & -r) ret += querySum(root[r], 0, all, x + 1, all);
for (--l; l; l -= l & -l) ret -= querySum(root[l], 0, all, x + 1, all);
return ret;
}
inline void modify(int x, int val, int cnt) {
for (; x <= n; x += x & -x) insert(root[x], 0, all, val, cnt);
}
inline void modify(int x, int y) {
int ov = b[dfn[x]];
a[x] = b[dfn[x]] = y;
modify(dfn[x], ov, -1);
modify(dfn[x], y, 1);
}
inline int queryGreater(int x, int y, int val) {
int ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
ans += greaterBit(dfn[top[y]], dfn[y], val);
y = fa[top[y]];
} else {
ans += greaterBit(dfn[top[x]], dfn[x], val);
x = fa[top[x]];
}
}
if (dep[x] < dep[y]) ans += greaterBit(dfn[x], dfn[y], val);
else ans += greaterBit(dfn[y], dfn[x], val);
return ans;
}
inline int lca(int x, int y) {
if (x == y) return x;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) y = fa[top[y]];
else x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
int tmp[maxn];
inline int force(int x, int y, int l, int k) {
int tp = 0;
for (; x ^ l; x = fa[x]) tmp[++tp] = a[x];
for (; y ^ l; y = fa[y]) tmp[++tp] = a[y];
tmp[++tp] = a[l];
std::nth_element(tmp + 1, tmp + k, tmp + tp + 1, std::greater<int>());
return tmp[k];
}
inline int queryKth(int x, int y, int k) {
int l = lca(x, y);
int cnt = dep[x] + dep[y] - 2 * dep[l] + 1;
if (cnt < k) return -1;
if (10 * cnt < logall * logall * logn * logn) return force(x, y, l, k);
int left = 0, right = all;
while (left <= right) {
int mid = (left + right) >> 1;
int g = queryGreater(x, y, mid);
if (g < k) right = mid - 1;
else left = mid + 1;
}
return right + 1;
}
int main() {
read(n, m);
rep(i, 1, n) read(a[i]), chkMax(all, a[i]);
++all;
double lg2 = log(2);
logn = log(n) / lg2;
logall = log(all) / lg2;
rep(i, 1, n - 1) {
int x, y; read(x, y);
ae(x, y);
}
dfs(1); dfs(1, 1);
rep(i, 1, n) modify(i, b[i], 1);
rep(i, 1, m) {
int k, x, y; read(k, x, y);
if (!k) modify(x, y);
else {
int ans = queryKth(x, y, k);
if (~ans) printf("%d\n", ans);
else puts("invalid request!");
}
}
return 0;
}
```
by GKxx @ 2018-10-04 20:55:52
@[GKxx](/space/show?uid=72071)
# 今天，我第二次看到了您诡异的码风。
# 您的代码如滔滔江水滚滚不绝，read重载5次，再加上诸多空格、空行，另我此生再不敢动码农一下，偷偷orz大佬，完了滚回去颓红题了……
by 引领天下 @ 2018-10-04 20:58:36
@[引领天下](/space/show?uid=39863) 。。。。。。
by GKxx @ 2018-10-04 20:59:26
%%%
by ciwomuli @ 2018-10-04 21:00:30
好了！！！我知道为什么了！！！
问题出在我的all这个变量
all的意思是值域最大值
但是我没有把后来修改的值也算到all上去
by GKxx @ 2018-10-05 01:55:53