# Codeforces Round #329 (Div. 2) D. Happy Tree Party

### 解法

HL分解して積を頑張って計算する。正攻法ではなさそう。

HL分解の説明についてはこっちに書いておいた。pekempey.hatenablog.com

LCA+eulertourも行ける気がする。（ただ0の逆元の対処が可能かは知らない）
こんな感じにルート間クエリが計算できる。

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

const ll mod1 = 2147483647;
const ll mod2 = 1224736769;
const ll mod3 = 2000000011;

const ll modpow(ll a, ll b, ll mod) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b /= 2;
}
return res;
}

const ll modinv(ll a, ll mod) {
return modpow(a, mod - 2, mod);
}

ll garner(ll a, ll b, ll mod1, ll mod2) {
ll x = (b - a) * modinv(mod1, mod2);
x %= mod2; x += mod2; x %= mod2;
return a + x * mod1;
}

struct lint {
ll x, y, z;
double w;
lint() : x(1), y(1), z(1), w(0) {}
lint(ll a) : x(a % mod1), y(a % mod2), z(a % mod3), w(log(a)) {}
lint operator *(lint b) {
lint res;
res.x = x * b.x % mod1;
res.y = y * b.y % mod2;
res.z = z * b.z % mod3;
res.w = w + b.w;
return res;
}
lint operator /(lint b) {
lint res;
res.x = x * modinv(b.x, mod1) % mod1;
res.y = y * modinv(b.y, mod2) % mod2;
res.z = z * modinv(b.z, mod3) % mod3;
res.w = w - b.w;
return res;
}
lint &operator *=(const lint &b) {
x = x * b.x % mod1;
y = y * b.y % mod2;
z = z * b.z % mod3;
w += b.w;
return *this;
}
lint &operator /=(const lint &b) {
x = x * modinv(b.x, mod1) % mod1;
y = y * modinv(b.y, mod2) % mod2;
z = z * modinv(b.z, mod3) % mod3;
w = w - b.w;
return *this;
}
operator ll() {
const double X = 18 * log(10) + log(2.0);
if (w >= X) return 2e18;
ll a = garner(x, y, mod1, mod2);
ll b = garner(y, z, mod2, mod3);
ll c = garner(z, x, mod3, mod1);
if (a == 0 && b == 0 && c == 0) return 0;
if (a != 0) return a;
if (b != 0) return b;
if (c != 0) return b;
}
};

struct LCA {
vector<vector<int>> G, parent;
vector<int> depth;
LCA(int n) : G(n), parent(24, vector<int>(n)), depth(n) {}
void add(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
void build(int root = 0) {
dfs(root, -1);
rep (i, 23) rep (j, G.size()) {
if (parent[i][j] == -1) parent[i + 1][j] = -1;
else parent[i + 1][j] = parent[i][parent[i][j]];
}
}
void dfs(int curr, int prev) {
parent[0][curr] = prev;
for (int next : G[curr]) if (next != prev) {
depth[next] = depth[curr] + 1;
dfs(next, curr);
}
}
int query(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
repr (i, 24) if (depth[u] - depth[v] >= 1 << i) {
u = parent[i][u];
}
if (u == v) return u;
repr (i, 24) if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
return parent[0][u];
}
};

struct HL {
vector<vector<int>> G, path;
vector<int> parent, head, order, heads, heavy, depth;
int root;
HL(int n) : G(n), heavy(n, -1), parent(n), head(n), order(n), path(n), depth(n) {}
void add(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
int dfs(int curr, int prev = -1) {
int res = 1;
parent[curr] = prev;
int maxv = -1;
for (int next : G[curr]) if (next != prev) {
int d = dfs(next, curr);
res += d;
if (maxv < d) maxv = d, heavy[curr] = next;
}
return res;
}
void dfs2(int curr, int prev = -1) {
for (int next : G[curr]) if (next != prev) {
if (next == heavy[curr]) {
order[next] = order[curr] + 1;
}
depth[next] = depth[curr] + (next != heavy[curr]);
dfs2(next, curr);
}
}
void build(int root = 0) {
this->root = root;
dfs(root);
dfs2(root);
}
struct Iterator {
int u, v;
HL *hl;
Iterator(HL *hl, int u, int v) : hl(hl), u(u), v(v) {}
// head, [from, to)
tuple<int, int, int> next() {
if (hl->depth[u] == hl->depth[v]) {
auto m = minmax(hl->order[u], hl->order[v]);
u = -1;
return make_tuple(hl->head[v], m.first, m.second + 1);
}
}
if (hl->depth[u] < hl->depth[v]) swap(u, v);
int pu = u;
return make_tuple(hl->head[pu], 0, hl->order[pu] + 1);
}
bool has_next() {
return u != -1;
}
};
Iterator iterator(int u, int v) {
return Iterator(this, u, v);
}
};

struct SegmentTree {
vector<lint> prod;
int size;

void init(int n) {
size = 1;
while (size < n) size *= 2;
prod.resize(size * 2);
}

void set(int k, ll v) {
k += size - 1;
prod[k] = lint(v);
}

void build() {
repr (k, size - 1) {
prod[k] = prod[k * 2 + 1] * prod[k * 2 + 2];
}
}

lint get(int k) {
k += size - 1;
return prod[k];
}

void update(int k, ll v) {
k += size - 1;
prod[k] = lint(v);
while (k) {
k = (k - 1) / 2;
prod[k] = prod[k * 2 + 1] * prod[k * 2 + 2];
}
}

lint query(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) return lint();
if (a <= l && r <= b) return prod[k];
lint x = query(a, b, k * 2 + 1, l, (l + r) / 2);
lint y = query(a, b, k * 2 + 2, (l + r) / 2, r);
return x * y;
}

lint query(int a, int b) {
return query(a, b, 0, 0, size);
}
};

struct HLSolver {
HL hl;
vector<SegmentTree> tr;
HLSolver(int n) : hl(n), tr(n) {}
void add(int u, int v) {
}
void build() {
hl.build();
for (int h : hl.heads) {
tr[h].init(hl.path[h].size());
}
}
void set(int u, ll x) {
}
void build_segment_tree() {
for (int h : hl.heads) {
tr[h].build();
}
}
void update(int u, ll x) {
}
lint get(int u) {
}
ll query(int u, int v, int l) {
lint res;
res /= get(l);
auto it = hl.iterator(u, v);
while (it.has_next()) {
int h, l, r;
tie(h, l, r) = it.next();
res *= tr[h].query(l, r);
}
return (ll)res;
}
};

int depth[202020];
vector<int> G[202020];

void dfs(int curr, int prev = -1) {
for (int next : G[curr]) if (next != prev) {
depth[next] = depth[curr] + 1;
dfs(next, curr);
}
}

int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> es(n - 1);
vector<ll> val(n - 1);
HLSolver hl(n);
LCA lca(n);
rep (i, n - 1) {
int u, v;
ll x;
scanf("%d %d %I64d", &u, &v, &x);
u--; v--;
G[u].push_back(v);
G[v].push_back(u);
es[i] = make_pair(u, v);
val[i] = x;
}
hl.build();
lca.build();
dfs(0);
rep (i, n - 1) {
int u, v;
tie(u, v) = es[i];
if (depth[u] > depth[v]) swap(es[i].first, es[i].second);
}
rep (i, n - 1) {
int u, v;
tie(u, v) = es[i];
hl.set(v, val[i]);
}
hl.build_segment_tree();

rep (i_, m) {
int qid;
scanf("%d", &qid);

if (qid == 1) {
int a, b;
ll y;
scanf("%d %d %I64d", &a, &b, &y);
a--; b--;
int l = lca.query(a, b);
ll ans = hl.query(a, b, l);
ans = y / ans;
printf("%I64d\n", ans);
} else {
int p;
ll c;
scanf("%d %I64d", &p, &c);
int u, v;
tie(u, v) = es[p - 1];
hl.update(v, c);
}
}
return 0;
}