Untitled

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
using namespace std;
 
const int MAX = 3e5 + 5;
ll dp[MAX][20];
vector<int> edges[MAX];
vector<ll> tree(MAX * 4);
vector<ll> lazy(MAX * 4);
vector<ll> v(MAX);
vector<int> parent(MAX);
vector<int> level(MAX);
vector<int> subg(MAX);
vector<int> heavy(MAX);
vector<int> reorder(MAX);
vector<int> top_chain(MAX);
int cnt = 0;
 
void push(int idx, int left, int right) {
    if (lazy[idx] != 0) {
        tree[idx] = lazy[idx];
        if (left != right) {
            lazy[idx * 2] = lazy[idx];
            lazy[idx * 2 + 1] = lazy[idx];
        }
        lazy[idx] = 0;
    }
 
    return;
}
 
void update(int idx, int left, int right, int a, int b, ll val) {
    push(idx, left, right);
    if (left > b || right < a) return;
 
    if (left >= a && right <= b) {
        tree[idx] += (right - left + 1) * val;
        if (left != right) {
            lazy[idx * 2] += val;
            lazy[idx * 2 + 1] += val;
        }
        return;
    }
 
    int mid = (left + right) / 2;
    update(idx * 2, left, mid, a, b, val);
    update(idx * 2 + 1, mid + 1, right, a, b, val);
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}
 
ll query(int idx, int left, int right, int a, int b) {
    push(idx, left, right);
    if (left > b || right < a) return 0;
    if (left >= a && right <= b) return tree[idx];
 
    int mid = (left + right) / 2;
    return query(idx * 2, left, mid, a, b) + query(idx * 2 + 1, mid + 1, right, a, b);
}
 
void dfs1(int a, int prev) {
    level[a] = level[prev] + 1;
    dp[a][0] = prev;
    for (int j = 1; j < 20; j++) {
        dp[a][j] = dp[dp[a][j - 1]][j - 1];
    }
 
    for (auto e : edges[a]) {
        if (e == prev) continue;
        dfs1(e, a);
    }
 
    return;
}
 
int lca(int a, int b) {
    if (level[a] < level[b]) swap(a, b);
    int diff = level[a] - level[b];
    for (int j = 0; j < 20; j++) {
        if (diff & 1 << j) a = dp[a][j];
    }
 
    if (a == b) return a;
    for (int j = 19; j >= 0; j--) {
        if (dp[a][j] == dp[b][j]) continue;
        a = dp[a][j];
        b = dp[b][j];
    }
 
    return dp[a][0];
}
 
void dfs2(int a, int prev) {
    parent[a] = prev;
    subg[a] = 1;
    for (auto e : edges[a]) {
        if (e == prev) continue;
        dfs2(e, a);
        subg[a] += subg[e];
        if (subg[e] > subg[heavy[a]]) heavy[a] = e;
    }
 
    return;
}
 
void dfs3(int a, int prev) {
    reorder[a] = ++cnt;
    if (heavy[a]) dfs3(heavy[a], a);
    for (auto e : edges[a]) {
        if (e == prev) continue;
        if (e == heavy[a]) continue;
        dfs3(e, a);
    }
 
    return;
}
 
void dfs4(int a, int prev) {
    for (auto e : edges[a]) {
        if (e == prev) continue;
        if (e == heavy[a]) top_chain[e] = top_chain[a];
        else top_chain[e] = e;
        dfs4(e, a);
    }
 
    return;
}
 
ll calc(int a, int c, int n) {
    ll ans = query(1, 0, n, reorder[a], reorder[a]);
    while(a != c) {
        if (top_chain[a] == a) {
            ans += query(1, 0, n, reorder[parent[a]], reorder[parent[a]]);
            a = parent[a];
        }
        else if (level[c] > level[top_chain[a]]){
            ans += query(1, 0, n, reorder[c], reorder[parent[a]]);
            a = c;
        }
        else {
            ans += query(1, 0, n, reorder[top_chain[a]], reorder[parent[a]]);
            a = top_chain[a];
        }
    }
 
    return ans;
}
 
void update_path(int a, int c, ll val, int n) {
    update(1, 0, n, reorder[a], reorder[a], val);
    while(a != c) {
        if (top_chain[a] == a) {
            update(1, 0, n, reorder[parent[a]], reorder[parent[a]], val);
            a = parent[a];
        }
        else if (level[c] > level[top_chain[a]]){
            update(1, 0, n, reorder[c], reorder[parent[a]], val);
            a = c;
        }
        else {
            update(1, 0, n, reorder[top_chain[a]], reorder[parent[a]], val);
            a = top_chain[a];
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q, a, b, t;
    ll x;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
 
        dfs1(1, 0);
        dfs2(1, 0);
        dfs3(1, 0);
        dfs4(1, 0);
 
    for (int i = 1; i <= n; i++) update(1, 0, n, reorder[i], reorder[i], v[i]);
 
    while(q--) {
        cin >> t;
        if (t == 1) {
            cin >> a >> b >> x;
            int c = lca(a, b);
            update_path(a, c, x, n);
            update_path(b, c, x, n);
            update_path(c, c, -x, n);
        }
        else {
            cin >> a >> b;
            int c = lca(a, b);
            ll ans = calc(a, c, n) + calc(b, c, n) - calc(c, c, n);
            cout << ans << "\n";
 
        }
    }
 
    return 0;
}