Shared code

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 9, LG = 18, inf = 1e9 + 9;

int n;

struct ST {

#define lc (n << 1)

#define rc ((n << 1) | 1)

  int t[4 * N];

  ST() {

    fill(t, t + 4 * N, -inf);

  }

  inline int combine(int a, int b) {

    return max(a, b); //merge left and right queries

  }

  inline void pull(int n) {

    t[n] = max(t[lc], t[rc]); //merge lower nodes of the tree to get the parent node

  }

  void build(int n, int b, int e, vector<int> &a) {

    if(b == e) {

      t[n] = a[b];

      return;

    }

    int mid = (b + e) >> 1;

    build(lc, b, mid, a);

    build(rc, mid + 1, e, a);

    pull(n);

  }

  void upd(int n, int b, int e, int i, int v) {

    if(b == e) {

      t[n] = v;

      return;

    }

    int mid = (b + e) >> 1;

    if(i <= mid) upd(lc, b, mid, i, v);

    else upd(rc, mid + 1, e, i, v);

    pull(n);

  }

  int query(int n, int b, int e, int i, int j) {

    if(i > e || b > j) return -inf;

    if(i <= b && e <= j) return t[n];

    int mid = (b + e) >> 1;

    return combine(query(lc, b, mid, i, j), query(rc, mid + 1, e, i, j));

  }

} t;

vector<int> g[N];

int par[N][LG + 1], dep[N], sz[N];

void dfs(int root) {

  vector<int> order;

  order.reserve(n);

  stack<int> s;

  s.push(root);

  par[root][0] = 0;

  dep[root] = 1;

  while(!s.empty()) {

    int u = s.top();
    s.pop();

    order.push_back(u);

    for(auto v : g[u]) if(v != par[u][0]) {

      par[v][0] = u;
      dep[v] = dep[u] + 1;

      for(int i = 1; i <= LG; i++)
        par[v][i] = par[par[v][i - 1]][i - 1];

      s.push(v);

    }

  }

  reverse(order.begin(), order.end());

  for(auto u : order) {

    sz[u] = 1;

    int heavy = -1;

    for(auto v : g[u]) {

      if(par[v][0] != u) continue;

      sz[u] += sz[v];

      if(heavy == -1 || sz[v] > sz[heavy])
        heavy = v;

    }

    if(heavy != -1) {

      auto it = find(g[u].begin(), g[u].end(), heavy);

      iter_swap(g[u].begin(), it);

    }

  }

}

int lca(int u, int v) {

  if (dep[u] < dep[v]) swap(u, v);

  for (int k = LG; k >= 0; k--) if (dep[par[u][k]] >= dep[v]) u = par[u][k];

  if (u == v) return u;

  for (int k = LG; k >= 0; k--) if (par[u][k] != par[v][k])
    u = par[u][k], v = par[v][k];

  return par[u][0];

}

int kth(int u, int k) {

  assert(k >= 0);

  for (int i = 0; i <= LG; i++)
    if (k & (1 << i)) u = par[u][i];

  return u;

}

int T, head[N], st[N], en[N];

void dfs_hld(int root) {

  stack<pair<int, int>> s;

  s.push({root, root});

  while(!s.empty()) {

    int u = s.top().first;
    int h = s.top().second;

    s.pop();

    while(u) {

      head[u] = h;
      st[u] = ++T;

      for(int i = (int)g[u].size() - 1; i >= 0; i--) {

        int v = g[u][i];

        if(v == par[u][0] || v == g[u][0]) continue;

        s.push({v, v});

      }

      if(g[u].empty() || g[u][0] == par[u][0]) break;

      u = g[u][0];

    }

  }

  for(int u = 1; u <= n; u++)
    en[u] = st[u] + sz[u] - 1;

}

int query_up(int u, int v) {

  int ans = -inf;

  while(head[u] != head[v]) {

    ans = max(ans, t.query(1, 1, n, st[head[u]], st[u]));

    u = par[head[u]][0];

  }

  ans = max(ans, t.query(1, 1, n, st[v], st[u]));

  return ans;

}

int query(int u, int v) {

  int l = lca(u, v);

  int ans = query_up(u, l);

  if (v != l)
    ans = max(ans, query_up(v, kth(v, dep[v] - dep[l] - 1)));

  return ans;

}

int32_t main() {

  ios_base::sync_with_stdio(0);

  cin.tie(0);

  int q;

  cin >> n >> q;

  vector<int> a(n + 1), b(n + 1);

  for (int i = 1; i <= n; i++)
    cin >> a[i];

  for (int i = 1; i < n; i++) {

    int u, v;

    cin >> u >> v;

    g[u].push_back(v);
    g[v].push_back(u);

  }

  dfs(1);

  dfs_hld(1);

  for(int i = 1; i <= n; i++)
    b[st[i]] = a[i];

  t.build(1, 1, n, b);

  while(q--) {

    int ty;

    cin >> ty;

    if(ty == 1) {

      int s, x;

      cin >> s >> x;

      t.upd(1, 1, n, st[s], x);

    } else {

      int u, v;

      cin >> u >> v;

      cout << query(u, v) << '\n';

    }

  }

  return 0;

}