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;
  using ll = long long;
  using ld = long double;
  using pi = pair<ll, ll>;
  using vi = vector<ll>;
  template <class T>
  using vc = vector<T>;
  template <class T>
  using vvc = vector<vc<T>>;
  template <class T>
  using vvvc = vector<vvc<T>>;
  template <class T>
  using vvvvc = vector<vvvc<T>>;
  template <class T>
  using vvvvvc = vector<vvvvc<T>>;
  template <class T>
  using pq = priority_queue<T>;
  template <class T>
  using pqg = priority_queue<T, vector<T>, greater<T>>;
  template <class T>
  T ceil(T x, T y) {
    assert(y >= 1);
    return (x > 0 ? (x + y - 1) / y : x / y);
  }
  template <class T>
  T floor(T x, T y) {
    assert(y >= 1);
    return (x > 0 ? x / y : (x - y + 1) / y);
  }
  void scan(int& a) { cin >> a; }
  void scan(long long& a) { cin >> a; }
  void scan(char& a) { cin >> a; }
  void scan(double& a) { cin >> a; }
  void scan(long double& a) { cin >> a; }
  void scan(string& a) { cin >> a; }
  template <class T, class S>
  void scan(pair<T, S>& p) {
    scan(p.first), scan(p.second);
  }
  template <class T>
  void scan(vector<T>& a) {
    for (auto& i : a) scan(i);
  }
  template <class T>
  void scan(T& a) {
    cin >> a;
  }
  void IN() {}
  template <class Head, class... Tail>
  void IN(Head& head, Tail&... tail) {
    scan(head);
    IN(tail...);
  }
  vi s_to_vi(string S, char first_char = 'a') {
    vi A(S.size());
    for (ll i = 0; (i) < (ll)(S.size()); ++(i)) {
      A[i] = S[i] - first_char;
    }
    return A;
  }
  template <typename T, typename U>
  ostream& operator<<(ostream& os, const pair<T, U>& A) {
    os << A.first << " " << A.second;
    return os;
  }
  template <typename T>
  ostream& operator<<(ostream& os, const vector<T>& A) {
    for (size_t i = 0; i < A.size(); i++) {
      if (i) os << " ";
      os << A[i];
    }
    return os;
  }
  void print() { cout << "\n"; }
  template <class Head, class... Tail>
  void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(Tail)) cout << " ";
    print(forward<Tail>(tail)...);
  }
  const string YESNO[2] = {"NO", "YES"};
  const string YesNo[2] = {"No", "Yes"};
  const string yesno[2] = {"no", "yes"};
  void YES(bool t = 1) { cout << YESNO[t] << endl; }
  void NO(bool t = 1) { YES(!t); }
  void Yes(bool t = 1) { cout << YesNo[t] << endl; }
  void No(bool t = 1) { Yes(!t); }
  void yes(bool t = 1) { cout << yesno[t] << endl; }
  void no(bool t = 1) { yes(!t); }
  template <typename T>
  vector<T> cumsum(vector<T> A) {
    ll N = A.size();
    vector<T> B(N + 1);
    B[0] = T(0);
    for (ll i = 0; (i) < (ll)(N); ++(i)) {
      B[i + 1] = B[i] + A[i];
    }
    return B;
  }
  vi bin_count(vi& A, ll size) {
    vi C(size);
    for (auto&& x : A) {
      ++C[x];
    }
    return C;
  }
  template <typename T>
  vi argsort(vector<T>& A) {
    vi ids(A.size());
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(),
         [&](ll i, ll j) { return A[i] < A[j] || (A[i] == A[j] && i < j); });
    return ids;
  }
  template <class T, class S>
  inline bool chmax(T& a, const S& b) {
    return (a < b ? a = b, 1 : 0);
  }
  template <class T, class S>
  inline bool chmin(T& a, const S& b) {
    return (a > b ? a = b, 1 : 0);
  }
  template <typename T>
  struct FenwickTree {
    vector<T> data;
    FenwickTree(int sz) { data.assign(++sz, 0); }
    T sum(int k) {
      T ret = 0;
      for (; k > 0; k -= k & -k) ret += data[k];
      return (ret);
    }
    void add(int k, T x) {
      for (++k; k < data.size(); k += k & -k) data[k] += x;
    }
    ll find_kth_element(T k) {
      auto N = data.size();
      ll x = 0;
      T sx = 0;
      ll dx = 1;
      while (2 * dx < N) dx *= 2;
      while (dx) {
        ll y = x + dx;
        if (y < N) {
          T sy = sx + data[y];
          if (sy < k) {
            swap(x, y);
            swap(sx, sy);
          }
        }
        dx /= 2;
      }
      return x;
    }
  };
  template <typename T>
  struct Edge {
    int frm, to;
    T cost;
    int id;
    Edge(int a, int b, T c, int d) : frm(a), to(b), cost(c), id(d) {}
  };
  template <typename T>
  struct Graph {
    int N, M;
    using edge_t = Edge<T>;
    vector<edge_t> edges;
    vector<vector<edge_t>> G;
    bool directed;
    Graph() {}
    Graph(int N, bool bl = false) : N(N), M(0), G(N), directed(bl) {}
    void add_edge(int frm, int to, T cost = 1, int i = -1) {
      if (i == -1) i = M;
      auto e = edge_t(frm, to, cost, i);
      edges.emplace_back(e);
      G[frm].emplace_back(e);
      if (!directed) {
        auto e_rev = edge_t(to, frm, cost, i);
        G[to].emplace_back(e_rev);
      }
      ++M;
    }
    void add(int frm, int to, T cost = 1, int i = -1) {
      if (i == -1) i = M;
      auto e = edge_t(frm, to, cost, i);
      edges.emplace_back(e);
      G[frm].emplace_back(e);
      if (!directed) {
        auto e_rev = edge_t(to, frm, cost, i);
        G[to].emplace_back(e_rev);
      }
      ++M;
    }
    void print(bool detail = false) {
      for (ll v = 0; (v) < (ll)(N); ++(v)) {
        cout << v << " :";
        for (auto e : G[v]) {
          if (detail)
            cout << " (" << e.frm << "," << e.to << "," << e.cost << "," << e.id
                 << ")";
          else
            cout << " " << e.to;
        }
        cout << "\n";
      }
    }
    int size() { return N; }
    vector<edge_t>& operator[](int v) { return G[v]; }
  };
  template <class T>
  struct EulerTour {
    T& G;
    int root;
    bool calc_anc;
    vector<int> V, VR, parent, LID, RID, depth;
    vector<vector<int>> ancestors;
    vector<vector<int>> ch;
    EulerTour() {}
    EulerTour(T& G, int root = 0, bool calc_anc = true)
        : G(G), root(root), calc_anc(calc_anc) {
      build();
    };
    void dfs(int v, int p) {
      LID[v] = V.size();
      V.emplace_back(v);
      parent[v] = p;
      depth[v] = (p == -1 ? 0 : depth[p] + 1);
      for (auto&& e : G[v]) {
        int w = e.to;
        if (w == p) continue;
        dfs(w, v);
      }
      RID[v] = V.size();
    }
    void build() {
      int N = G.N;
      V.reserve(N);
      parent.resize(N);
      LID.resize(N);
      RID.resize(N);
      depth.resize(N);
      parent[root] = -1;
      depth[root] = 0;
      dfs(root, -1);
      VR = V;
      reverse(VR.begin(), VR.end());
      if (calc_anc) {
        for (ll k = 0; (k) < (ll)(20); ++(k))
          ancestors.emplace_back(vector<int>(N));
        ancestors[0] = parent;
        for (ll k = (1); (k) < (ll)(20); ++(k)) {
          for (ll v = 0; (v) < (ll)(G.N); ++(v)) {
            int w = ancestors[k - 1][v];
            ancestors[k][v] = (w == -1 ? -1 : ancestors[k - 1][w]);
          }
        }
      }
    }
    int LCA(int a, int b) {
      assert(calc_anc);
      if (depth[a] > depth[b]) swap(a, b);
      auto n = depth[b] - depth[a];
      for (ll k = 0; (k) < (ll)(20); ++(k)) {
        if (n & 1 << k) b = ancestors[k][b];
      }
      if (a == b) return a;
      for (ll k = (ll)(20) - 1; (k) >= 0; --(k)) {
        if (ancestors[k][a] != ancestors[k][b]) {
          a = ancestors[k][a];
          b = ancestors[k][b];
        }
      }
      return parent[a];
    }
    int LA(int v, int n) {
      for (ll k = 0; (k) < (ll)(20); ++(k))
        if (n & 1 << k) {
          v = ancestors[k][v];
          if (v == -1) return -1;
        }
      return v;
    }
    int dist(int a, int b) {
      int c = LCA(a, b);
      return depth[a] + depth[b] - 2 * depth[c];
    }
    bool in_subtree(int a, int b) { return LID[b] <= LID[a] && LID[a] < RID[b]; }
    int move(int a, int b) {
      assert(a != b);
      return (in_subtree(b, a) ? LA(b, depth[b] - depth[a] - 1) : parent[a]);
    }
  };
  template <class T>
  struct EulerTour_e {
    T& G;
    int root;
    vector<int> tour, parent, LID, RID, depth;
    EulerTour_e(T& G, int root = 0) : G(G), root(root) { build(); };
    void dfs(int v, int p) {
      LID[v] = tour.size();
      tour.emplace_back(v);
      parent[v] = p;
      depth[v] = (p == -1 ? 0 : depth[p] + 1);
      for (auto&& e : G[v]) {
        int w = e.to;
        if (w == p) continue;
        dfs(w, v);
      }
      RID[v] = tour.size();
      tour.emplace_back(~v);
    }
    void build() {
      int N = G.N;
      tour.reserve(N * 2);
      parent.resize(N);
      LID.resize(N);
      RID.resize(N);
      depth.resize(N);
      parent[root] = -1;
      depth[root] = 0;
      dfs(root, -1);
    }
  };
  void solve() {
    ll N, Q;
    IN(N, Q);
    vector<ll> A(N);
    IN(A);
    for (auto&& x : A) x = abs(x);
    Graph<int> G(N);
    for (ll _ = 0; (_) < (ll)(N - 1); ++(_)) {
      ll a, b;
      IN(a, b);
      G.add(--a, --b);
    }
    EulerTour<Graph<int>> ET0(G);
    EulerTour_e<Graph<int>> ET(G);
    auto& LID = ET.LID;
    auto& RID = ET.RID;
    auto& dep = ET0.depth;
    FenwickTree<ll> bit(N + N + 10);
    for (ll v = 0; (v) < (ll)(N); ++(v)) {
      bit.add(LID[v], A[v]);
      bit.add(RID[v], -A[v]);
    }
    for (ll _ = 0; (_) < (ll)(Q); ++(_)) {
      ll t, a, b;
      IN(t, a, b);
      if (t == 1) {
        ll v = a - 1;
        bit.add(LID[v], -A[v]);
        bit.add(RID[v], +A[v]);
        A[v] = abs(b);
        bit.add(LID[v], +A[v]);
        bit.add(RID[v], -A[v]);
      } else {
        --a, --b;
        ll ANS = [&]() -> ll {
          if (dep[a] > dep[b]) swap(a, b);
          if (a == b) return 0;
          ll lca = ET0.LCA(a, b);
          if (lca == a) {
            ll x = bit.sum(LID[b]) - bit.sum(LID[a] + 1);
            x *= 2;
            x += A[b];
            x += A[a];
            return x;
          }
          ll x = bit.sum(LID[a]) - bit.sum(LID[lca] + 1);
          x += bit.sum(LID[b]) - bit.sum(LID[lca] + 1);
          x += A[lca];
          x *= 2;
          x += A[a];
          x += A[b];
          return x;
        }();
        print(ANS);
      }
    }
  }
  signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(15);
    solve();
    return 0;
  }
  