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 long long MAXN = 2e5 + 5;
  const long long SQRTN = 1003;
  const long long LOGN = 22;
  const double PI = acos(-1);
  const long long INF = 1e18;
  const long long MOD = 1e9 + 7;
  const long long FMOD = 998244353;
  const double eps = 1e-9;
  void __print(long long x) { cerr << x; }
  void __print(long x) { cerr << x; }
  void __print(unsigned x) { cerr << x; }
  void __print(unsigned long x) { cerr << x; }
  void __print(unsigned long long x) { cerr << x; }
  void __print(float x) { cerr << x; }
  void __print(double x) { cerr << x; }
  void __print(long double x) { cerr << x; }
  void __print(char x) { cerr << '\'' << x << '\''; }
  void __print(const char *x) { cerr << '\"' << x << '\"'; }
  void __print(const string &x) { cerr << '\"' << x << '\"'; }
  void __print(bool x) { cerr << (x ? "true" : "false"); }
  template <typename T, typename V>
  void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
  }
  template <typename T>
  void __print(const T &x) {
    long long f = 0;
    cerr << '{';
    for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
  }
  void _print() { cerr << "]\n"; }
  template <typename T, typename... V>
  void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
  }
  mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
  template <typename T>
  T gcd(T a, T b) {
    if (b == 0) return a;
    a %= b;
    return gcd(b, a);
  }
  template <typename T>
  T lcm(T a, T b) {
    return (a * (b / gcd(a, b)));
  }
  long long add(long long a, long long b, long long c = MOD) {
    long long res = a + b;
    return (res >= c ? res % c : res);
  }
  long long sub(long long a, long long b, long long c = MOD) {
    long long res;
    if (abs(a - b) < c)
      res = a - b;
    else
      res = (a - b) % c;
    return (res < 0 ? res + c : res);
  }
  long long mul(long long a, long long b, long long c = MOD) {
    long long res = (long long)a * b;
    return (res >= c ? res % c : res);
  }
  long long muln(long long a, long long b, long long c = MOD) {
    long long res = (long long)a * b;
    return ((res % c) + c) % c;
  }
  long long mulmod(long long a, long long b, long long m = MOD) {
    long long q = (long long)(((long double)a * (long double)b) / (long double)m);
    long long r = a * b - q * m;
    if (r > m) r %= m;
    if (r < 0) r += m;
    return r;
  }
  template <typename T>
  T binpow(T e, T n) {
    T x = 1, p = e;
    while (n) {
      if (n & 1) x = x * p;
      p = p * p;
      n >>= 1;
    }
    return x;
  }
  template <typename T>
  T binpow2(T e, T n, T m = MOD) {
    T x = 1, p = e;
    while (n) {
      if (n & 1) x = mul(x, p, m);
      p = mul(p, p, m);
      n >>= 1;
    }
    return x;
  }
  template <typename T>
  T extended_euclid(T a, T b, T &x, T &y) {
    T xx = 0, yy = 1;
    y = 0;
    x = 1;
    while (b) {
      T q = a / b, t = b;
      b = a % b;
      a = t;
      t = xx;
      xx = x - q * xx;
      x = t;
      t = yy;
      yy = y - q * yy;
      y = t;
    }
    return a;
  }
  template <typename T>
  T mod_inverse(T a, T n = MOD) {
    T x, y, z = 0;
    T d = extended_euclid(a, n, x, y);
    return (d > 1 ? -1 : sub(x, z, n));
  }
  const long long FACSZ = 1e4;
  long long fact[FACSZ], ifact[FACSZ];
  void precom(long long c = MOD) {
    fact[0] = 1;
    for (long long i = 1; i < FACSZ; i++) fact[i] = mul(fact[i - 1], i, c);
    ifact[FACSZ - 1] = mod_inverse(fact[FACSZ - 1], c);
    for (long long i = FACSZ - 1 - 1; i >= 0; i--) {
      ifact[i] = mul(i + 1, ifact[i + 1], c);
    }
  }
  vector<long long> primes;
  void prime_precom() {
    primes.push_back(2);
    for (long long x = 3; primes.size() <= MAXN; x += 2) {
      bool isPrime = true;
      for (auto p : primes) {
        if (x % p == 0) {
          isPrime = false;
          break;
        }
        if (p * p > x) {
          break;
        }
      }
      if (isPrime) {
        primes.push_back(x);
      }
    }
  }
  long long ncr(long long n, long long k) {
    if (n < k) return 0;
    if (k == 0) return 1;
    long long res = 1;
    if (k > n - k) k = n - k;
    for (long long i = 0; i < k; ++i) {
      res *= (n - i);
      res /= (i + 1);
    }
    return res;
  }
  long long ncr_modp(long long n, long long k, long long c = MOD) {
    if (n < k) return 0;
    if (k == 0) return 1;
    long long res = 1;
    if (k > n - k) k = n - k;
    for (long long i = 0; i < k; ++i) {
      res = mul(res, n - i, c);
      res = mul(res, binpow2(i + 1, c - 2, c), c);
    }
    return res;
  }
  vector<long long> factors;
  void factorize(long long a) {
    factors.clear();
    for (long long i = 1; i * i <= a; i++) {
      if (a % i == 0) {
        factors.push_back(i);
        factors.push_back(a / i);
      }
    }
    sort(factors.begin(), factors.end());
  }
  long long ncr_precom(long long n, long long r, long long c = MOD) {
    return mul(mul(ifact[r], ifact[n - r], c), fact[n], c);
  }
  long long ceil(long long a, long long b) { return (a + b - 1) / b; }
  bool is_prime(long long n) {
    for (long long i = 2; i * i <= n; i++) {
      if (n % i == 0) {
        return 0;
      }
    }
    return 1;
  }
  bool diophantine_checker(long long a, long long b, long long n) {
    for (long long i = 0; i * a <= n; i++) {
      if ((n - (i * a)) % b == 0) {
        return true;
      }
    }
    return false;
  }
  long long count_divisors(long long n) {
    long long c;
    long long ans = 1;
    for (long long i = 2; i * i <= n; i++) {
      c = 0;
      while (n % i == 0) {
        c++;
        n /= i;
      }
      ans *= (c + 1);
    }
    if (n > 2) {
      return ans * 2;
    }
    return ans;
  }
  string to_binary(long long n) {
    string r;
    while (n != 0) {
      r = (n % 2 == 0 ? "0" : "1") + r;
      n /= 2;
    }
    return r;
  }
  bool ispower2(long long x) { return x && (!(x & (x - 1))); }
  vector<long long> spf;
  void sieve() {
    spf.resize(MAXN);
    spf[1] = 1;
    for (long long i = 2; i < MAXN; i++) {
      spf[i] = i;
    }
    for (long long i = 4; i < MAXN; i += 2) {
      spf[i] = 2;
    }
    for (long long i = 3; i * i <= MAXN; i++) {
      if (spf[i] == i) {
        for (long long j = i * i; j < MAXN; j += i) {
          if (spf[j] == j) {
            spf[j] = i;
          }
        }
      }
    }
  }
  void pfactor(long long x, vector<long long> &ret) {
    while (x != 1) {
      ret.push_back(spf[x]);
      x = x / spf[x];
    }
  }
  vector<long long> v[MAXN];
  vector<long long> par(MAXN);
  long long start;
  vector<long long> a(MAXN);
  vector<long long> flat_tree(MAXN);
  vector<long long> in(MAXN), out(MAXN);
  void dfs1(long long node, long long p = 0) {
    par[node] = p;
    in[node] = ++start;
    flat_tree[start] = abs(a[node]);
    for (auto child : v[node]) {
      if (child ^ p) {
        dfs1(child, node);
      }
    }
    out[node] = ++start;
    flat_tree[start] = -abs(a[node]);
  }
  long long dp[MAXN][LOGN];
  vector<long long> depth(MAXN);
  void dfs(long long node, long long p = 0) {
    depth[node] = depth[p] + 1;
    dp[node][0] = p;
    for (long long i = 1; i < LOGN; i++) {
      dp[node][i] = dp[dp[node][i - 1]][i - 1];
    }
    for (auto child : v[node]) {
      if (child == p) continue;
      dfs(child, node);
    }
  }
  long long ancestor(long long node, long long k) {
    for (long long i = 0; i < LOGN && node; i++) {
      if (k & (1ll << i)) {
        node = dp[node][i];
      }
    }
    return (node == 0 ? -1 : node);
  }
  long long lca(long long node1, long long node2) {
    if (depth[node1] < depth[node2]) {
      swap(node2, node1);
    }
    node1 = ancestor(node1, depth[node1] - depth[node2]);
    if (node1 == node2) return node1;
    for (long long i = LOGN - 1; i >= 0; i--) {
      if (dp[node1][i] != dp[node2][i]) {
        node1 = dp[node1][i];
        node2 = dp[node2][i];
      }
    }
    return dp[node1][0];
  }
  template <class T>
  struct fenwick_tree {
   public:
    fenwick_tree() : _n(0) {}
    fenwick_tree(long long n) : _n(n), data(n) {}
    void add(long long i, T delta) {
      assert(0 <= i && i < _n);
      i++;
      while (i <= _n) {
        data[i - 1] += (delta);
        i += i & -i;
      }
    }
    T sum(long long l, long long r) {
      assert(0 <= l && l <= r && r <= _n);
      return sum(r) - sum(l);
    }
  
   private:
    long long _n;
    vector<T> data;
    T sum(long long r) {
      T s = 0;
      while (r > 0) {
        s += data[r - 1];
        r -= r & -r;
      }
      return s;
    }
  };
  void solvethetestcase() {
    long long n, q;
    cin >> n >> q;
    for (long long i = 0; i < n; i++) {
      cin >> a[i + 1];
    }
    for (long long i = 0; i < n - 1; i++) {
      long long a, b;
      cin >> a >> b;
      v[a].push_back(b);
      v[b].push_back(a);
    }
    dfs1(1);
    dfs(1);
    fenwick_tree<long long> ft(2 * n + 2);
    for (long long i = 0; i < 2 * n + 1; i++) {
      ft.add(i, flat_tree[i]);
    }
    while (q--) {
      long long op;
      cin >> op;
      if (op == 1) {
        long long u, x;
        cin >> u >> x;
        long long i1 = in[u];
        long long i2 = out[u];
        long long v1 = ft.sum(i1, i1 + 1);
        long long v2 = ft.sum(i2, i2 + 1);
        ft.add(i1, -v1);
        ft.add(i2, -v2);
        ft.add(i1, abs(x));
        ft.add(i2, -abs(x));
      } else {
        long long e1, e2;
        cin >> e1 >> e2;
        long long l = lca(e1, e2);
        if (l == e1 || l == e2) {
          if (l == e2) {
            swap(e1, e2);
          }
          if (e1 == e2) {
            cout << 0 << "\n";
            continue;
          }
          cout << ft.sum(in[e1], in[e2] + 1ll) +
                      ((in[e1] + 1 < in[e2]) ? ft.sum(in[e1] + 1, in[e2]) : 0ll)
               << "\n";
        } else {
          cout << ft.sum(in[l], in[e1] + 1ll) + ft.sum(in[l], in[e2] + 1ll) +
                      ((in[l] + 1ll < in[e1]) ? ft.sum(in[l] + 1ll, in[e1])
                                              : 0ll) +
                      ((in[l] + 1ll < in[e2]) ? ft.sum(in[l] + 1ll, in[e2]) : 0ll)
               << "\n";
        }
      }
    }
  }
  signed main() {
    cout << fixed << setprecision(12);
    ;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long t = 1;
    for (long long testcase = 1; testcase < t + 1; testcase++) {
      solvethetestcase();
    }
  }
  