#include namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; vector euler_tour_vertices(const vector>& tree, int root=0) { const int n = tree.size(); assert(n > 0); vector res; res.reserve(2 * n - 1); // 1 + 2|E| vector> st; st.reserve(n); st.emplace_back(root, 0); while(!st.empty()) { auto& [u, i] = st.back(); res.emplace_back(u); while(true) { if (i == (int)tree[u].size()) { st.pop_back(); break; } int v = tree[u][i++]; const int sz = st.size(); if (sz >= 2 && v == st[sz - 2].first) continue; st.emplace_back(v, 0); break; } } return res; } vector vertex_indices(const vector& et) { const int n = *max_element(et.begin(), et.end()) + 1; vector res(n); for (int i = (int)et.size() - 1; i >= 0; i--) res[et[i]] = i; return res; } template struct DisjointSparseTable { const int n; const vector msb; const vector> d; DisjointSparseTable(vector a) : n(a.size()), msb(build_msb_table(n)), d(build_table(move(a))) {} vector build_msb_table(int n) { if (n <= 1) return {}; unsigned char k_max = 32 - __builtin_clz(n - 1); vector res(1 << k_max); unsigned char* p = res.data(); for (unsigned char k = 0; k < k_max; k++) { memset(p + (1U << k), k, 1U << k); } return res; } vector> build_table(vector a) { const int n = a.size(); vector> res(1); if (n >= 2) { const int i_max = n - 1, k_max = 32 - __builtin_clz(i_max); res.resize(k_max); for (int k = 1; k < k_max; k++) { vector t(i_max >> k & 1 ? n : i_max & ~0U << k); for (int c = 1 << k; c < n; c += 1 << (k + 1)) { int l = c - (1 << k); int r = min(n, c + (1 << k)); t[c - 1] = a[c - 1]; for (int i = c - 2; i >= l; i--) t[i] = op(a[i], t[i + 1]); t[c] = a[c]; for (int i = c + 1; i < r; i++) t[i] = op(t[i - 1], a[i]); } res[k] = move(t); } } res[0] = move(a); return res; } S query(int l, int r) { return query_closed(l, r - 1); } S query_closed(int l, int r) { assert(0 <= l && l <= r && r < n); if (l == r) return d[0][l]; auto k = msb[l ^ r]; return op(d[k][l], d[k][r]); } }; int op(int x, int y) { return min(x, y); } struct HLD { const vector>& to; int root, n; vector sz, parent, depth, idx, ridx, head, inv; HLD(const vector>& to, int root=0) : to(to), root(root), n(to.size()), sz(n), parent(n), depth(n), idx(n), ridx(n), head(n), inv(n) { init_tree_data(root, -1, 0); int nxt = 0; assign_idx(root, root, nxt); } void init_tree_data(int u, int p, int d) { parent[u] = p; depth[u] = d; int s = 1; for (int v: to[u]) if (v != p) { init_tree_data(v, u, d+1); s += sz[v]; } sz[u] = s; } void assign_idx(int u, int h, int& nxt, int p=-1) { head[u] = h; idx[u] = nxt; inv[nxt] = u; nxt++; int heaviest = -1; int mxweight = 0; for (int v: to[u]) if (v != p) { if (sz[v] > mxweight) { heaviest = v; mxweight = sz[v]; } } if (heaviest != -1) { assign_idx(heaviest, h, nxt, u); for (int v: to[u]) if (v != p && v != heaviest) { assign_idx(v, v, nxt, u); } } ridx[u] = nxt; } int lca(int u, int v) { while (head[u] != head[v]) { if (depth[head[u]] > depth[head[v]]) { u = parent[head[u]]; } else { v = parent[head[v]]; } } return depth[u] < depth[v] ? u : v; } // returns reference to tuple of (path fragments from x upto lca (excluding lca), those from y, lca) // storage of retval is reused to avoid creating short vectors on each query tuple>, vector>, int> paths_res; auto& paths(int x, int y) { auto& [x_paths, y_paths, lca] = paths_res; x_paths.clear(); y_paths.clear(); while (head[x] != head[y]) { int hx = head[x], hy = head[y]; if (depth[hx] > depth[hy]) { x_paths.emplace_back(x, hx); x = parent[hx]; } else { y_paths.emplace_back(y, hy); y = parent[hy]; } } if (depth[x] > depth[y]) { x_paths.emplace_back(x, inv[idx[y] + 1]); x = y; } else if (depth[x] < depth[y]) { y_paths.emplace_back(y, inv[idx[x] + 1]); y = x; } lca = x; return paths_res; } int dist(int u, int v) { int w = lca(u, v); return depth[u] + depth[v] - 2 * depth[w]; } template int max_ancestor(int v, F f) { if (!f(v)) return -1; int hv = head[v]; int p = parent[hv]; while (p != -1 && f(p)) { v = p; hv = head[v]; p = parent[hv]; } int il = idx[hv] - 1, ir = idx[v]; while (ir - il > 1) { int ic = (il + ir) / 2; (f(inv[ic]) ? ir : il) = ic; } return inv[ir]; } int ascend(int v, int k) { assert(depth[v] >= k); int td = depth[v] - k; int hv = head[v]; while (depth[hv] > td) { v = parent[hv]; hv = head[v]; } int rest = depth[v] - td; return inv[idx[v] - rest]; } int move_to(int u, int v, int by) { int l = lca(u, v); int du = depth[u] - depth[l]; int dv = depth[v] - depth[l]; assert(by <= du + dv); if (by <= du) return ascend(u, by); else return ascend(v, du + dv - by); } }; template struct array_map { int state[element_size]; // -1 if not in set else index in elems pair elems[element_size]; int size = 0; array_map() { memset(state, -1, sizeof(int) * element_size); } bool contains(int x) { return state[x] != -1; } pair* begin() { return elems; } pair* end() { return elems + size; } void clear() { while(size) state[elems[--size].first] = -1; } void erase(int x) { // not tested int idx = state[x]; if (idx != -1) { state[x] = -1; size--; if (idx != size) { int y = elems[size].first; state[y] = idx; elems[idx] = move(elems[size]); } } } T& operator[](int x) { if (state[x] == -1) { state[x] = size; elems[size].first = x; elems[size].second = T(); size++; } return elems[state[x]].second; } }; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; VL a(n); rep(i, n) cin >> a[i]; VVI to(n); rep(_, n - 1) { int u, v; cin >> u >> v; u--, v--; to[u].emplace_back(v); to[v].emplace_back(u); } HLD hld(to); VI et = euler_tour_vertices(to); VI pos = vertex_indices(et); DisjointSparseTable dst([&]() { assert(ssize(et) == 2 * n - 1); VI d(2 * n - 1); rep(i, 2 * n - 1) d[i] = hld.depth[et[i]]; return d; }()); auto dist = [&](int u, int v) { int iu = pos[u], iv = pos[v]; if (iu > iv) swap(iu, iv); return hld.depth[u] + hld.depth[v] - 2 * dst.query_closed(iu, iv); }; VL a2, s1, s2; constexpr int B = 600; static array_map upd; rep(iq, q) { if (iq % B == 0) { for (auto [k, v] : upd) a[k] += v; upd.clear(); a2.assign(n, 0); rep(u, n) for (int v : to[u]) a2[v] += a[u]; s1 = a; s2 = a2; rep(i, n) if (i) { int u = hld.inv[i]; s1[u] += s1[hld.parent[u]]; s2[u] += s2[hld.parent[u]]; } } int type; cin >> type; if (type == 0) { int v, x; cin >> v >> x; v--; upd[v] += x; } else { int u, v; cin >> u >> v; u--, v--; int l = hld.lca(u, v); ll ans = s2[u] + s2[v] - 2 * s2[l] + a2[l] + a[u] + a[v]; ans -= s1[u] + s1[v] - 2 * s1[l] + a[l]; for (auto [w, val] : upd) { int d = 1001001001; chmin(d, (dist(w, u) + dist(w, l) - (hld.depth[u] - hld.depth[l])) / 2); chmin(d, (dist(w, v) + dist(w, l) - (hld.depth[v] - hld.depth[l])) / 2); if (d <= 1) ans += val; } cout << ans << '\n'; } } }