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;
  inline long long read() {
    char s;
    long long k = 0, base = 1;
    while ((s = getchar()) != '-' && s != EOF && !isdigit(s))
      ;
    if (s == EOF) exit(0);
    if (s == '-') base = -1, s = getchar();
    while (isdigit(s)) {
      k = k * 10 + (s ^ 48);
      s = getchar();
    }
    return k * base;
  }
  void write(long long x) {
    if (x < 0) {
      putchar('-');
      write(-x);
    } else {
      if (x / 10) write(x / 10);
      putchar(x % 10 + '0');
    }
  }
  const long long maxn = 1e5 + 100;
  long long l[maxn << 2], r[maxn << 2];
  long long tree[maxn << 2], lazy[maxn << 2];
  long long n, m, root, x, y, z, bj;
  long long D[maxn];
  long long fa[maxn], deep[maxn], sz[maxn], hson[maxn];
  long long to[maxn << 1], ne[maxn << 1], po[maxn << 1], id1;
  long long top[maxn], id[maxn], rel[maxn], tot;
  inline void add(long long x, long long y) {
    ++id1;
    to[id1] = y;
    ne[id1] = po[x];
    po[x] = id1;
    ++id1;
    to[id1] = x;
    ne[id1] = po[y];
    po[y] = id1;
  }
  void dfs1(long long x) {
    sz[x] = 1;
    deep[x] = deep[fa[x]] + 1;
    hson[x] = 0;
    for (long long i = po[x]; i; i = ne[i]) {
      if (to[i] != fa[x]) {
        fa[to[i]] = x;
        dfs1(to[i]);
        sz[x] += sz[to[i]];
        if (sz[to[i]] > sz[hson[x]]) hson[x] = to[i];
      }
    }
    return;
  }
  void dfs2(long long x, long long last) {
    top[x] = last;
    id[x] = ++tot;
    rel[tot] = x;
    if (hson[x] == 0) return;
    dfs2(hson[x], last);
    for (long long i = po[x]; i; i = ne[i]) {
      if (to[i] != fa[x] && to[i] != hson[x]) dfs2(to[i], to[i]);
    }
  }
  void bt(long long x, long long y, long long d) {
    l[d] = x;
    r[d] = y;
    if (x == y) {
      tree[d] = D[rel[x]];
      return;
    }
    long long mid = (x + y) >> 1;
    bt(x, mid, d << 1);
    bt(mid + 1, y, d << 1 | 1);
    tree[d] = tree[d << 1] + tree[d << 1 | 1];
    return;
  }
  void push(long long d) {
    if (lazy[d] != 0) {
      lazy[d << 1] += lazy[d];
      lazy[d << 1 | 1] += lazy[d];
      tree[d << 1] += (r[d << 1] - l[d << 1] + 1) * lazy[d];
      tree[d << 1 | 1] += (r[d << 1 | 1] - l[d << 1 | 1] + 1) * lazy[d];
      tree[d] = tree[d << 1] + tree[d << 1 | 1];
      lazy[d] = 0;
    }
    return;
  }
  void xg(long long x, long long y, long long d, long long z) {
    if (x <= l[d] && r[d] <= y) {
      tree[d] += z * (r[d] - l[d] + 1);
      lazy[d] += z;
      return;
    }
    push(d);
    long long mid = (l[d] + r[d]) >> 1;
    if (y > mid) xg(max(mid + 1, x), y, d << 1 | 1, z);
    if (x <= mid) xg(x, min(y, mid), d << 1, z);
    tree[d] = tree[d << 1] + tree[d << 1 | 1];
    return;
  }
  long long cx(long long x, long long y, long long d) {
    if (x <= l[d] && r[d] <= y) {
      return tree[d];
    }
    push(d);
    long long mid = (l[d] + r[d]) >> 1;
    long long s = 0;
    if (y > mid) s += cx(max(mid + 1, x), y, d << 1 | 1);
    if (x <= mid) s += cx(x, min(y, mid), d << 1);
    return s;
  }
  void add1() {
    long long X = read();
    long long Y = X;
    long long Z = abs(read());
    Z = Z - D[X];
    D[X] += Z;
    long long tx = top[X], ty = top[Y];
    while (tx != ty) {
      if (deep[tx] < deep[ty]) swap(tx, ty), swap(X, Y);
      xg(id[tx], id[X], 1, Z);
      X = fa[tx];
      tx = top[X];
    }
    if (deep[X] < deep[Y]) swap(X, Y);
    xg(id[Y], id[X], 1, Z);
  }
  void ans1() {
    long long X = read(), Y = read();
    long long s = 0;
    long long XX = X, YY = Y;
    long long tx = top[X], ty = top[Y];
    while (tx != ty) {
      if (deep[tx] < deep[ty]) swap(tx, ty), swap(X, Y);
      s += cx(id[tx], id[X], 1);
      X = fa[tx];
      tx = top[X];
    }
    if (deep[X] < deep[Y]) swap(X, Y);
    s += cx(id[Y], id[X], 1);
    s = s * 2 - D[XX] - D[YY];
    write(s);
    putchar('\n');
  }
  signed main() {
    n = read();
    m = read();
    root = 1;
    for (long long i = 1; i <= n; i++) D[i] = abs(read());
    for (long long i = 1; i < n; i++) add(read(), read());
    fa[root] = 0;
    dfs1(root);
    dfs2(root, root);
    bt(1, n, 1);
    while (m--) {
      bj = read();
      if (bj == 1)
        add1();
      else if (bj == 2)
        ans1();
    }
    return 0;
  }
  