#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_
#include <stdio.h>
#include <iostream>
constexpr unsigned __int128 toUInt128(const char *s) {
unsigned __int128 x = 0;
for (; *s; ++s) x = x * 10 + (*s - '0');
return x;
}
constexpr __int128 toInt128(const char *s) {
if (*s == '-') return -toInt128(s + 1);
__int128 x = 0;
for (; *s; ++s) x = x * 10 + (*s - '0');
return x;
}
unsigned __int128 inUInt128() {
static char buf[41];
scanf("%s", buf);
return toUInt128(buf);
}
__int128 inInt128() {
static char buf[41];
scanf("%s", buf);
return toInt128(buf);
}
void out(unsigned __int128 x) {
static char buf[41];
int len = 0;
do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
if (x < 0) {
putchar('-');
out(-static_cast<unsigned __int128>(x));
} else {
out(static_cast<unsigned __int128>(x));
}
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
static char buf[41];
int len = 0;
do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
for (int i = len; --i >= 0; ) os << buf[i];
return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
if (x < 0) {
os << '-' << -static_cast<unsigned __int128>(x);
} else {
os << static_cast<unsigned __int128>(x);
}
return os;
}
#endif // LIBRA_OTHER_INT128_H_
struct Hld {
int n, rt;
// needs to be tree
// vertex lists
// modified in build(rt) (parent removed, heavy child first)
vector<vector<int>> graph;
vector<int> sz, par, dep;
int zeit;
vector<int> dis, fin, sid;
// head vertex (minimum depth) in heavy path
vector<int> head;
Hld() : n(0), rt(-1), zeit(0) {}
explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfsSz(int u) {
sz[u] = 1;
for (const int v : graph[u]) {
auto it = std::find(graph[v].begin(), graph[v].end(), u);
if (it != graph[v].end()) graph[v].erase(it);
par[v] = u;
dep[v] = dep[u] + 1;
dfsSz(v);
sz[u] += sz[v];
}
}
void dfsHld(int u) {
dis[u] = zeit++;
const int deg = graph[u].size();
if (deg > 0) {
int vm = graph[u][0];
int jm = 0;
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
if (sz[vm] < sz[v]) {
vm = v;
jm = j;
}
}
swap(graph[u][0], graph[u][jm]);
head[vm] = head[u];
dfsHld(vm);
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
head[v] = v;
dfsHld(v);
}
}
fin[u] = zeit;
}
void build(int rt_) {
assert(0 <= rt_); assert(rt_ < n);
rt = rt_;
sz.assign(n, 0);
par.assign(n, -1);
dep.assign(n, -1);
dep[rt] = 0;
dfsSz(rt);
zeit = 0;
dis.assign(n, -1);
fin.assign(n, -1);
head.assign(n, -1);
head[rt] = rt;
dfsHld(rt);
assert(zeit == n);
sid.assign(n, -1);
for (int u = 0; u < n; ++u) sid[dis[u]] = u;
}
friend ostream &operator<<(ostream &os, const Hld &hld) {
const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
vector<string> ss(2 * maxDep + 1);
int pos = 0, maxPos = 0;
for (int j = 0; j < hld.n; ++j) {
const int u = hld.sid[j];
const int d = hld.dep[u];
if (hld.head[u] == u) {
if (j != 0) {
pos = maxPos + 1;
ss[2 * d - 1].resize(pos, '-');
ss[2 * d - 1] += '+';
}
} else {
ss[2 * d - 1].resize(pos, ' ');
ss[2 * d - 1] += '|';
}
ss[2 * d].resize(pos, ' ');
ss[2 * d] += std::to_string(u);
if (maxPos < static_cast<int>(ss[2 * d].size())) {
maxPos = ss[2 * d].size();
}
}
for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
return os;
}
bool contains(int u, int v) const {
return (dis[u] <= dis[v] && dis[v] < fin[u]);
}
int lca(int u, int v) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
return (dis[u] > dis[v]) ? v : u;
}
int jumpUp(int u, int d) const {
assert(0 <= u); assert(u < n);
assert(d >= 0);
if (dep[u] < d) return -1;
const int tar = dep[u] - d;
for (u = head[u]; ; u = head[par[u]]) {
if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
}
}
int jump(int u, int v, int d) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
assert(d >= 0);
const int l = lca(u, v);
const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
if (d <= du) {
return jumpUp(u, d);
} else if (d <= du + dv) {
return jumpUp(v, du + dv - d);
} else {
return -1;
}
}
// [u, v) or [u, v]
template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
assert(contains(v, u));
for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
if (inclusive) {
f(dis[v], dis[u] + 1);
} else {
if (v != u) f(dis[v] + 1, dis[u] + 1);
}
}
// not path order, include lca(u, v) or not
template <class F> void doPath(int u, int v, bool inclusive, F f) const {
const int l = lca(u, v);
doPathUp(u, l, false, f);
doPathUp(v, l, inclusive, f);
}
// (vs, ps): compressed tree
// vs: DFS order (sorted by dis)
// vs[ps[x]]: the parent of vs[x]
// ids[vs[x]] = x, not set for non-tree vertex
vector<int> ids;
pair<vector<int>, vector<int>> compress(vector<int> us) {
// O(n) first time
ids.resize(n, -1);
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
int usLen = us.size();
assert(usLen >= 1);
for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
usLen = us.size();
for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
vector<int> ps(usLen, -1);
for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
return make_pair(us, ps);
}
};
////////////////////////////////////////////////////////////////////////////////
// point add, rectangle sum
template <class X, class Y, class T> struct Bit2d {
vector<X> xs;
vector<pair<Y, X>> yxs;
vector<vector<Y>> yss;
int m;
vector<int> ns;
vector<vector<T>> bit;
Bit2d() {}
void book(X x, Y y) {
xs.push_back(x);
yxs.emplace_back(y, x);
}
void build() {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
m = xs.size();
yss.assign(m, {});
sort(yxs.begin(), yxs.end());
for (const auto &yx : yxs) {
const int x = yx.second, y = yx.first;
const int a = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
assert(a < m); assert(xs[a] == x);
for (int u = a; u < m; u |= u + 1) yss[u].push_back(y);
}
ns.assign(m, 0);
bit.assign(m, {});
for (int u = 0; u < m; ++u) {
yss[u].erase(unique(yss[u].begin(), yss[u].end()), yss[u].end());
ns[u] = yss[u].size();
bit[u].assign(ns[u], T());
}
}
void add(int x, int y, T val) {
const int a = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
assert(a < m); assert(xs[a] == x);
for (int u = a; u < m; u |= u + 1) {
const int b = lower_bound(yss[u].begin(), yss[u].end(), y) - yss[u].begin();
assert(b < ns[u]); assert(yss[u][b] == y);
for (int v = b; v < ns[u]; v |= v + 1) bit[u][v] += val;
}
}
T get(int x0, int x1, int y0, int y1) const {
const int a0 = lower_bound(xs.begin(), xs.end(), x0) - xs.begin();
const int a1 = lower_bound(xs.begin(), xs.end(), x1) - xs.begin();
T ret = T();
for (int u = a0; u; u &= u - 1) ret -= get(u - 1, y0, y1);
for (int u = a1; u; u &= u - 1) ret += get(u - 1, y0, y1);
return ret;
}
private:
T get(int u, int y0, int y1) const {
T ret = T();
const int b0 = lower_bound(yss[u].begin(), yss[u].end(), y0) - yss[u].begin();
const int b1 = lower_bound(yss[u].begin(), yss[u].end(), y1) - yss[u].begin();
for (int v = b0; v; v &= v - 1) ret -= bit[u][v - 1];
for (int v = b1; v; v &= v - 1) ret += bit[u][v - 1];
return ret;
}
};
using P = pair<int, Int>;
void operator+=(P &a, const P &b) {
a.first += b.first;
a.second += b.second;
}
void operator-=(P &a, const P &b) {
a.first -= b.first;
a.second -= b.second;
}
int N, Q;
vector<int> A, B;
vector<int> C;
vector<int> O, U, V, D;
vector<Int> M;
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
C.resize(N);
for (int u = 0; u < N; ++u) {
scanf("%d", &C[u]);
}
O.assign(Q, -1);
U.assign(Q, -1);
V.assign(Q, -1);
D.assign(Q, -1);
M.assign(Q, -1);
for (int q = 0; q < Q; ++q) {
scanf("%d", &O[q]);
if (O[q] == 1) {
scanf("%d%d", &U[q], &D[q]);
--U[q];
} else if (O[q] == 2) {
scanf("%d%d%lld", &U[q], &V[q], &M[q]);
--U[q];
--V[q];
} else {
assert(false);
}
}
Hld hld(N);
for (int i = 0; i < N - 1; ++i) {
hld.ae(A[i], B[i]);
}
hld.build(0);
Bit2d<int, int, P> bit;
Bit2d<int, int, __int128> bit2;
vector<int> cs;
for (int j = 0; j < N; ++j) {
const int u = hld.sid[j];
bit.book(j, -C[u]);
bit2.book(j, -C[u]);
cs.push_back(C[u]);
}
for (int q = 0; q < Q; ++q) if (O[q] == 1) {
bit.book(hld.dis[U[q]], -D[q]);
bit2.book(hld.dis[U[q]], -D[q]);
cs.push_back(D[q]);
}
bit.build();
bit2.build();
cs.push_back(0);
sort(cs.begin(), cs.end());
cs.erase(unique(cs.begin(), cs.end()), cs.end());
const int csLen = cs.size();
// cerr<<"cs = "<<cs<<endl;
__int128 tot = 0;
auto add = [&](int j, int sig, Int d) -> void {
tot += sig * d * d;
bit.add(j, -d, P(sig, sig * d));
bit2.add(j, -d, sig * d * d);
};
auto ds = C;
for (int j = 0; j < N; ++j) {
const int u = hld.sid[j];
add(j, +1, ds[u]);
}
for (int q = 0; q < Q; ++q) {
if (O[q] == 1) {
const int u = U[q];
const int j = hld.dis[u];
add(j, -1, ds[u]);
add(j, +1, ds[u] = D[q]);
} else {
// cerr<<COLOR("33")<<"ds = "<<ds<<", tot = "<<tot<<COLOR()<<endl;
vector<pair<int, int>> ps;
hld.doPath(U[q], V[q], true, [&](int l, int r) -> void {
ps.emplace_back(l, r);
});
int lo = -1, hi = csLen - 1;
for (; lo + 1 < hi; ) {
const int mid = (lo + hi) / 2;
P sum(0, 0);
for (const auto &p : ps) {
sum += bit.get(p.first, p.second, -cs.back(), -cs[mid]);
}
const Int cost = sum.second - (Int)sum.first * cs[mid];
// cerr<<"mid = "<<mid<<", cs[mid] = "<<cs[mid]<<", sum = "<<sum<<", cost = "<<cost<<endl;
((cost <= M[q]) ? hi : lo) = mid;
}
{
__int128 now = tot;
P sum(0, 0);
for (const auto &p : ps) {
sum += bit.get(p.first, p.second, -cs.back(), -cs[hi]);
now -= bit2.get(p.first, p.second, -cs.back(), -cs[hi]);
}
Int m = M[q];
m -= (sum.second - (Int)sum.first * cs[hi]);
// cerr<<"hi = "<<hi<<", cs[hi] = "<<cs[hi]<<", sum = "<<sum<<", now = "<<now<<", m = "<<m<<endl;
assert(m >= 0);
if (lo >= 0) {
int here = 0;
for (const auto &p : ps) {
here += bit.get(p.first, p.second, -cs.back(), -cs[lo]).first;
}
// cerr<<"here = "<<here<<endl;
assert(here > 0);
const Int quo = m / here, rem = m % here;
now -= (__int128)(here - sum.first) * cs[hi] * cs[hi];
now += (__int128)(here - rem) * (cs[hi] - quo) * (cs[hi] - quo);
now += (__int128)rem * (cs[hi] - quo - 1) * (cs[hi] - quo - 1);
}
out(now);
puts("");
}
}
}
}
return 0;
}