#include
using namespace std;
const int buf_len = 45678;
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() {
if (++ bufb == bufe)
bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin);
}
#define readInt(x) {
register int s(0), neg(0);
while (!isdigit(*bufb)) {
if (*bufb == ‘-’)
neg = 1;
readBuf();
}
do {
s = s * 10 + *bufb - 48;
readBuf();
} while (isdigit(*bufb));
if (neg)
x = -s;
else
x = s;
}
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
struct edge { int t; edge *ne; };
struct seg { int l, r; dint z, cn, sn, mn, cp, sp; seg *ch[2]; };
const int maxn = 100003; const dint dinf = 0x3f3f3f3f3f3f3fll;
int n, m, a[maxn]; int d[maxn], fa[maxn], sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn]; int dbuf_arr[maxn], *dbuf(dbuf_arr), *ab[maxn]; edge ebuf_arr[maxn « 1], *ebuf(ebuf_arr), *head[maxn]; seg sbuf_arr[maxn « 2], *sbuf(sbuf_arr), *rt[maxn];
inline void addEdge(int u, int v) { ebuf-> t = v; ebuf-> ne = head[u]; head[u] = ebuf ++; }
#define midp(p) ((p->l+p->r)»1) inline void update(seg* p) { p-> cn = p-> ch[0]-> cn + p-> ch[1]-> cn; p-> sn = p-> ch[0]-> sn + p-> ch[1]-> sn + p-> cn * p-> z; p-> mn = max(p-> ch[0]-> mn, p-> ch[1]-> mn); p-> cp = p-> ch[0]-> cp + p-> ch[1]-> cp; p-> sp = p-> ch[0]-> sp + p-> ch[1]-> sp + p-> cp * p-> z; } inline void addTo(seg* p, int z) { p-> z += z; p-> sn += p-> cn * z; p-> sp += p-> cp * z; if (p-> mn > -dinf) p-> mn += z; } inline void pushDown(seg* p) { if (p-> z) { addTo(p-> ch[0], p-> z); addTo(p-> ch[1], p-> z); p-> z = 0; } }
inline seg* sgtBuild(int l, int r, int* ab) { seg* p(sbuf ++); p-> l = l, p-> r = r, p-> z = 0; if (l + 1 < r) { p-> ch[0] = sgtBuild(l, midp(p), ab); p-> ch[1] = sgtBuild(midp(p), r, ab); update(p); } else { if (ab[l] >= 0) { p-> cn = 0, p-> sn = 0, p-> mn = -dinf; p-> cp = 1, p-> sp = ab[l]; } else { p-> cn = 1, p-> sn = p-> mn = ab[l]; p-> cp = 0, p-> sp = 0; } } return p; } inline void sgtCheck(seg* p) { if (p-> l + 1 == p-> r) { if (p-> mn >= 0) { p-> cp = 1, p-> sp = p-> mn; p-> cn = 0, p-> sn = 0, p-> mn = -dinf; } } else { pushDown(p); while (p-> mn >= 0) { sgtCheck(p-> ch[p-> mn == p-> ch[1]-> mn]); update(p); } } } inline void sgtAdd(seg* p, int l, int r, int z) { if (p-> l == l && p-> r == r) { addTo(p, z); sgtCheck(p); } else { pushDown(p); if (r <= midp(p) || l >= midp(p)) sgtAdd(p-> ch[l >= midp(p)], l, r, z); else sgtAdd(p-> ch[0], l, midp(p), z), sgtAdd(p-> ch[1], midp(p), r, z); update(p); sgtCheck(p); } } inline dint sgtQry(seg* p, int l, int r) { if (p-> l == l && p-> r == r) { return p-> sp - p-> sn; } else { pushDown(p); if (r <= midp(p) || l >= midp(p)) return sgtQry(p-> ch[l >= midp(p)], l, r); else return sgtQry(p-> ch[0], l, midp(p)) + sgtQry(p-> ch[1], midp(p), r); } }
#define cpos(p) (d[p]-d[ch[fc[p]]])
void divide() { static int q[maxn]; int hd(0), tl(1); fa[q[hd] = 1] = 0; d[1] = 1; while (hd < tl) { int p(q[hd ++]); for (edge* e = head[p]; e; e = e-> ne) if (e-> t != fa[p]) { fa[e-> t] = p; d[e-> t] = d[p] + 1; q[tl ++] = e-> t; } } tc = 0; for (int i = tl - 1; i >= 0; – i) { int p(q[i]), z(-1); sz[p] = 1; for (edge* e = head[p]; e; e = e-> ne) if (e-> t != fa[p]) { sz[p] += sz[e-> t]; if (z == -1 || sz[e-> t] > sz[z]) z = e-> t; } if (z == -1) cl[fc[p] = ++ tc] = 1; else ++ cl[fc[p] = fc[z]]; ch[fc[p]] = p; } for (int i = 1; i <= tc; ++ i) ab[i] = dbuf, dbuf += cl[i]; for (int i = 1; i <= n; ++ i) ab[fc[i]][cpos(i)] = a[i]; for (int i = 1; i <= tc; ++ i) rt[i] = sgtBuild(0, cl[i], ab[i]); }
int main() { #ifdef LAEKOV_LOCAL freopen(".in", “r”, stdin); #endif
readInt(n);
readInt(m);
for (int i = 1; i <= n; ++ i)
readInt(a[i]);
for (int i = 1; i < n; ++ i) {
int u, v;
readInt(u);
readInt(v);
addEdge(u, v);
addEdge(v, u);
}
divide();
while (m --) {
int opt, u, v, w;
readInt(opt);
readInt(u);
readInt(v);
if (opt == 1) {
readInt(w);
while (fc[u] != fc[v]) {
if (d[ch[fc[u]]] < d[ch[fc[v]]])
swap(u, v);
sgtAdd(rt[fc[u]], 0, cpos(u) + 1, w);
u = fa[ch[fc[u]]];
}
if (d[u] > d[v])
swap(u, v);
sgtAdd(rt[fc[u]], cpos(u), cpos(v) + 1, w);
}
else if (opt == 2) {
dint ans(0);
while (fc[u] != fc[v]) {
if (d[ch[fc[u]]] < d[ch[fc[v]]])
swap(u, v);
ans += sgtQry(rt[fc[u]], 0, cpos(u) + 1);
u = fa[ch[fc[u]]];
}
if (d[u] > d[v])
swap(u, v);
ans += sgtQry(rt[fc[u]], cpos(u), cpos(v) + 1);
printf(lld "\n", ans);
}
}
}