description: Chanek Jones is back, helping his long-lost relative Indiana Jones, to find a secret treasure in a maze buried below a desert full of illusions.
  
  The map of the labyrinth forms a tree with n rooms numbered from 1 to n and n - 1 tunnels connecting them such that it is possible to travel between each pair of rooms through several tunnels.
  
  The i-th room (1 ≤ i ≤ n) has a_i illusion rate. To go from the x-th room to the y-th room, there must exist a tunnel between x and y, and it takes max(|a_x + a_y|, |a_x - a_y|) energy. |z| denotes the absolute value of z.
  
  To prevent grave robbers, the maze can change the illusion rate of any room in it. Chanek and Indiana would ask q queries.
  
  There are two types of queries to be done:
  
    * 1\ u\ c — The illusion rate of the x-th room is changed to c (1 ≤ u ≤ n, 0 ≤ |c| ≤ 10^9). 
    * 2\ u\ v — Chanek and Indiana ask you the minimum sum of energy needed to take the secret treasure at room v if they are initially at room u (1 ≤ u, v ≤ n). 
  
  
  
  Help them, so you can get a portion of the treasure!
  
  Input
  
  The first line contains two integers n and q (2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5) — the number of rooms in the maze and the number of queries.
  
  The second line contains n integers a_1, a_2, …, a_n (0 ≤ |a_i| ≤ 10^9) — inital illusion rate of each room.
  
  The i-th of the next n-1 lines contains two integers s_i and t_i (1 ≤ s_i, t_i ≤ n), meaning there is a tunnel connecting s_i-th room and t_i-th room. The given edges form a tree.
  
  The next q lines contain the query as described. The given queries are valid.
  
  Output
  
  For each type 2 query, output a line containing an integer — the minimum sum of energy needed for Chanek and Indiana to take the secret treasure.
  
  Example
  
  Input
  
  
  6 4
  10 -9 2 -1 4 -6
  1 5
  5 4
  5 6
  6 2
  6 3
  2 1 2
  1 1 -3
  2 1 2
  2 3 3
  
  
  Output
  
  
  39
  32
  0
  
  Note
  
  <image>
  
  In the first query, their movement from the 1-st to the 2-nd room is as follows.
  
    * 1 → 5 — takes max(|10 + 4|, |10 - 4|) = 14 energy. 
    * 5 → 6 — takes max(|4 + (-6)|, |4 - (-6)|) = 10 energy. 
    * 6 → 2 — takes max(|-6 + (-9)|, |-6 - (-9)|) = 15 energy. 
  
  In total, it takes 39 energy.
  
  In the second query, the illusion rate of the 1-st room changes from 10 to -3.
  
  In the third query, their movement from the 1-st to the 2-nd room is as follows.
  
    * 1 → 5 — takes max(|-3 + 4|, |-3 - 4|) = 7 energy. 
    * 5 → 6 — takes max(|4 + (-6)|, |4 - (-6)|) = 10 energy. 
    * 6 → 2 — takes max(|-6 + (-9)|, |-6 - (-9)|) = 15 energy. 
  
  
  
  Now, it takes 32 energy.
solution: #include <bits/stdc++.h>
  using namespace std;
  const double EPS = 1e-12;
  const int INF = 1e9 + 10;
  template <typename T>
  using MinPQ = priority_queue<T, vector<T>, greater<T>>;
  template <class T>
  struct FenwickTree {
    int n;
    vector<T> a;
    vector<T> f;
    FenwickTree(int n = 0) { Reset(n); }
    void Reset(int n) {
      this->n = n;
      a.assign(n + 1, 0);
      f.assign(n + 1, 0);
    }
    T Query(int i) {
      assert(i >= 0 && i <= n);
      T r = 0;
      for (; i > 0; i -= LowBit(i)) {
        r += f[i];
      }
      return r;
    }
    T Query(int l, int r) {
      T res = Query(r);
      if (l > 1) res -= Query(l - 1);
      return res;
    }
    T QueryAll() { return Query(n); }
    void Add(int i, T x) {
      assert(i >= 1 && i <= n);
      a[i] += x;
      for (; i <= n; i += LowBit(i)) {
        f[i] += x;
      }
    }
    void Set(int i, T x) { Add(i, x - a[i]); }
  
   private:
    static inline int LowBit(int i) { return i & -i; }
  };
  template <class T>
  struct Rmq {
    int n;
    vector<T> a;
    vector<vector<int>> f;
    vector<int> f_idx;
    Rmq(const vector<T>& a = {}) { Reset(a); }
    void Reset(const vector<T>& a) {
      this->a = a;
      n = int((a).size());
      vector<int> cur(n);
      iota((cur).begin(), (cur).end(), 0);
      f.clear();
      f.push_back(move(cur));
      if (n == 0) return;
      for (int p = 1;; ++p) {
        int len = 1 << p;
        int len2 = len >> 1;
        cur.resize(n - len + 1);
        for (int i = 0; i < int((cur).size()); ++i) {
          int u1 = f[p - 1][i], u2 = f[p - 1][i + len - len2];
          if (a[u1] < a[u2])
            cur[i] = u1;
          else
            cur[i] = u2;
        }
        f.push_back(move(cur));
        if ((len << 1) >= n) break;
      }
      f_idx.resize(n + 1);
      f_idx[0] = 0;
      for (int i = 1; i <= n; ++i) {
        int p = f_idx[i >> 1];
        while (1 << (p + 1) < i) ++p;
        f_idx[i] = p;
      }
    }
    int QueryIndex(int l, int r) {
      if (l > r) swap(l, r);
      int len = r - l + 1;
      int p = f_idx[len];
      int u1 = f[p][l], u2 = f[p][r - (1 << p) + 1];
      if (a[u1] < a[u2]) return u1;
      return u2;
    }
  };
  int n;
  vector<int> a;
  vector<pair<int, int>> edges;
  vector<vector<int>> child;
  vector<int> par;
  vector<int> depth;
  vector<int> e_seq;
  vector<pair<int, int>> e_pos;
  vector<int> u_seq;
  vector<int> u_pos;
  struct EdgeStatus {
    set<int> updated;
    set<int> not_updated;
  };
  vector<EdgeStatus> child_edge_status;
  int Cost(int ei) {
    assert(ei >= 0 && ei < n - 1);
    int u = edges[ei].first, v = edges[ei].second;
    return max(abs(a[u] + a[v]), abs(a[u] - a[v]));
  }
  void Dfs(int u, int pu) {
    u_pos[u] = int((u_seq).size());
    u_seq.push_back(u);
    for (int i = 0; i < int((child[u]).size()); ++i) {
      int ei = child[u][i];
      auto& e = edges[ei];
      if (e.first == pu) {
        par[u] = ei;
        child[u][i] = child[u].back();
        child[u].pop_back();
        i--;
        continue;
      }
      if (e.second == u) swap(e.first, e.second);
      depth[e.second] = depth[u] + 1;
      e_pos[ei].first = int((e_seq).size());
      e_seq.push_back(ei);
      Dfs(e.second, u);
      e_pos[ei].second = int((e_seq).size());
      e_seq.push_back(ei);
      u_seq.push_back(u);
    }
  }
  void Solve() {
    int q;
    scanf("%d%d", &n, &q);
    a.resize(n);
    for (auto& x : (a)) scanf("%d", &x);
    edges.resize(n - 1);
    child.assign(n, {});
    for (int i = 0; i < n - 1; ++i) {
      auto& e = edges[i];
      scanf("%d%d", &e.first, &e.second);
      e.first--;
      e.second--;
      child[e.first].push_back(i);
      child[e.second].push_back(i);
    }
    e_seq.clear();
    e_seq.reserve(n * 2);
    e_pos.resize(n - 1);
    u_seq.clear();
    u_seq.reserve(n * 2);
    u_pos.resize(n);
    par.resize(n);
    depth.resize(n);
    depth[0] = 0;
    par[0] = -1;
    Dfs(0, -1);
    vector<int> depth_seq(int((u_seq).size()));
    for (int i = 0; i < int((u_seq).size()); ++i) {
      depth_seq[i] = depth[u_seq[i]];
    }
    Rmq<int> rmq(depth_seq);
    vector<int> cost_seq(int((e_seq).size()));
    for (int i = 0; i < n - 1; ++i) {
      int w = Cost(i);
      cost_seq[e_pos[i].first] = w;
      cost_seq[e_pos[i].second] = -w;
    }
    FenwickTree<long long> cost_ft;
    cost_ft.Reset(int((cost_seq).size()));
    for (int i = 0; i < int((cost_seq).size()); ++i) {
      cost_ft.Set(i + 1, cost_seq[i]);
    }
    child_edge_status.resize(n);
    for (int i = 0; i < n; ++i) {
      child_edge_status[i].not_updated.clear();
      child_edge_status[i].updated =
          set<int>((child[i]).begin(), (child[i]).end());
    }
    set<int> e_seq_idx_to_update;
    auto UpdateEdge = [&](int ei) {
      int w = Cost(ei);
      cost_ft.Set(e_pos[ei].first + 1, w);
      cost_ft.Set(e_pos[ei].second + 1, -w);
      int u = edges[ei].first;
      child_edge_status[u].updated.insert(ei);
      child_edge_status[u].not_updated.erase(ei);
    };
    auto Query = [&](int u, int v) -> long long {
      int up = u_pos[u], vp = u_pos[v];
      assert(up <= vp);
      if (up == vp) return 0;
      vp--;
      auto it = e_seq_idx_to_update.lower_bound(up);
      while (it != e_seq_idx_to_update.end() && *it <= vp) {
        UpdateEdge(e_seq[*it]);
        it = e_seq_idx_to_update.erase(it);
      }
      return cost_ft.Query(up + 1, vp + 1);
    };
    while (q--) {
      int op, u, v;
      scanf("%d%d%d", &op, &u, &v);
      --u;
      if (op == 1) {
        a[u] = v;
        child_edge_status[u].not_updated.insert(
            (child_edge_status[u].updated).begin(),
            (child_edge_status[u].updated).end());
        for (auto& ei : (child_edge_status[u].updated)) {
          e_seq_idx_to_update.insert(e_pos[ei].first);
          e_seq_idx_to_update.insert(e_pos[ei].second);
        }
        child_edge_status[u].updated.clear();
        if (par[u] >= 0) {
          int ei = par[u];
          int pu = edges[ei].first;
          child_edge_status[u].not_updated.insert(ei);
          child_edge_status[u].updated.erase(ei);
          e_seq_idx_to_update.insert(e_pos[ei].first);
          e_seq_idx_to_update.insert(e_pos[ei].second);
        }
      } else {
        --v;
        int lca = u_seq[rmq.QueryIndex(u_pos[u], u_pos[v])];
        42;
        long long w = Query(lca, u) + Query(lca, v);
        printf("%lld\n", w);
      }
    }
  }
  int main() {
    int t = 1;
    for (int i = 1; i <= t; ++i) {
      Solve();
    }
    return 0;
  }
  