Juanzhang

#include <bits/stdc++.h>
using namespace std;

const int maxn = 8e4 + 10;
int tid[maxn], fa[maxn], sz[maxn], dep[maxn], son[maxn], top[maxn];
int n, m, len, qtot, val[maxn], ans[maxn], Q[maxn * 3], Q1[maxn * 3], Q2[maxn * 3];

struct node {
  int k, u, v, tid;

  node() {}
  node(int _k, int _u, int _v, int _t) :
    k(_k), u(_u), v(_v), tid(_t) {}
} a[maxn * 3];

struct BIT {
  int now, c[maxn], T[maxn];

  void clr() { now++; }

  void _add(int pos, int v) {
    for (; pos <= n; pos += pos & -pos) {
      T[pos] < now ? c[pos] = v, T[pos] = now : c[pos] += v;
    }
  }

  int query(int pos) {
    int res = 0;
    for (; pos; pos &= pos - 1) {
      if (T[pos] == now) res += c[pos];
    }
    return res;
  }

  void add(int u, int x) {
    _add(tid[u], x), _add(tid[u] + sz[u], -x);
  }
} bit;

vector <int> e[maxn];

int dfs1(int u, int f) {
  fa[u] = f, dep[u] = dep[f] + 1;
  for (int v : e[u]) {
    if (v != f) {
      sz[u] += dfs1(v, u);
      if (sz[son[u]] < sz[v]) son[u] = v;
    }
  }
  return ++sz[u];
}

void dfs2(int u, int tp) {
  static int now;
  tid[u] = ++now, top[u] = tp;
  if (son[u]) dfs2(son[u], tp);
  for (int v : e[u]) {
    if (v != fa[u] && v != son[u]) {
      dfs2(v, v);
    }
  }
}

int lca(int u, int v) {
  for (; top[u] != top[v]; u = fa[top[u]]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
  }
  return dep[u] < dep[v] ? u : v;
}

int query(int u, int v) {
  int _lca = lca(u, v);
  return bit.query(tid[u]) + bit.query(tid[v]) - bit.query(tid[_lca]) - bit.query(tid[fa[_lca]]);
}

void divide(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (int i = l; i <= r; i++) {
      ans[a[Q[i]].tid] = ql;
    }
    return;
  }
  bit.clr();
  int mid = (ql + qr) >> 1, p1 = 0, p2 = 0;
  for (int i = l; i <= r; i++) {
    node &tmp = a[Q[i]];
    if (!tmp.tid) {
      tmp.v > mid ? bit.add(tmp.u, tmp.k), Q2[++p2] = Q[i] : Q1[++p1] = Q[i];
    } else {
      int s = query(tmp.u, tmp.v);
      tmp.k > s ? Q1[++p1] = Q[i], tmp.k -= s : Q2[++p2] = Q[i];
    }
  }
  for (int i = 1; i <= p1; i++) {
    Q[l + i - 1] = Q1[i];
  }
  for (int i = 1; i <= p2; i++) {
    Q[r - p2 + i] = Q2[i];
  }
  divide(l, l + p1 - 1, ql, mid);
  divide(l + p1, r, mid + 1, qr);
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", val + i);
    a[++len] = node(1, i, val[i], 0);
  }
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    e[u].push_back(v), e[v].push_back(u);
  }
  dfs1(1, 0), dfs2(1, 1);
  for (int i = 1; i <= n; i++) {
    bit.add(i, 1);
  }
  for (int i = 1; i <= m; i++) {
    int k, u, v;
    scanf("%d %d %d", &k, &u, &v);
    if (!k) {
      a[++len] = node(-1, u, val[u], 0);
      a[++len] = node(1, u, val[u] = v, 0);
    } else {
      if (query(u, v) < k) {
        ans[++qtot] = -1;
      } else {
        a[++len] = node(k, u, v, ++qtot);
      }
    }
  }
  for (int i = 1; i <= len; i++) {
    Q[i] = i;
  }
  divide(1, len, 0, 1e8);
  for (int i = 1; i <= qtot; i++) {
    if (~ans[i]) {
      printf("%d\n", ans[i]);
    } else {
      puts("invalid request!");
    }
  }
  return 0;
}