题面
题解
我们发现，对于除法有效的xi最小为2，yi最多除log次就会变成0，所以我们可以每次找路径上下一个>=2的xi，暴力除，当发现y=0时就停止
于是我们维护每个点向上走一直走到根最近的一条数字大于1的边，存下该边的下端点，每当有一条边数字大于1，就要更新它的下端点子树中每一个的最近边，这个可以把点按照dfs序排序后用线段树做区间修改，单点查询
但是题目中的修改操作很特殊，每次会将一条边上的数字变小，后面一旦变为1了就不好维护，所以我决定倒着来（感性理解，把进度条从后往前拖），先把操作输入完，把每条边的数字先变为最小，从后往前处理询问，这样就相当于只有把xi变大的操作，就很好维护了。
（线段树一个运算符打错了，调了一晚上QAQ
CODE
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<algorithm>
#define MAXN 200005
#define MAXM 200005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x)&(x))
//#define int LL
//#pragma GCC optimize(2)
using namespace std;
inline LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}
while(s >= '0' && s <= '9') {x = x * 10 + (s - '0');s = getchar();}
return x * f;
}
const int jzm = 1000000007;
int n,m,i,j,s,o,k,M;
int u[MAXN],v[MAXN];
LL x[MAXN];
struct cz{
int k,u,v;
LL y;
}q[MAXN];
vector<int> g[MAXN];
int d[MAXN],f[MAXN][20],dfn[MAXN],id[MAXN],rr[MAXN],cnt;
LL fe[MAXN];
int tre[MAXN<<2];
int bing(int a,int b) {return d[a] > d[b] ? a : b;}
void maketree(int n) {M = 1;while(M < n + 2) M <<= 1;}
void addtree(int l,int r,int y) {
int s = M + l - 1,t = M + r + 1;
while(s || t) {
if((s>>1) ^ (t>>1)) {
if(!(s & 1)) tre[s ^ 1] = bing(tre[s ^ 1],y);
if(t & 1) tre[t ^ 1] = bing(tre[t ^ 1],y);
}
else break;
s >>= 1;t >>= 1;
}
return ;
}
int findt(int x) {
int s = M + x;int as = 0;
while(s) as = bing(as,tre[s]),s >>= 1;
return as;
}
void dfs(int x,int fa) {
d[x] = d[fa] + 1;
f[x][0] = fa;
dfn[x] = ++ cnt;
id[cnt] = x;
for(int i = 1;i <= 18;i ++) f[x][i] = f[f[x][i-1]][i-1];
for(int i = 0;i < g[x].size();i ++) {
if(g[x][i] != fa)
dfs(g[x][i],x);
}
rr[x] = cnt;
return ;
}
int lca(int a,int b) {
if(d[b] > d[a]) swap(a,b);
if(d[a] > d[b]) {
for(int i = 18;i >= 0;i --) {
if(d[f[a][i]] >= d[b]) {
a = f[a][i];
}
}
}
if(a == b) return a;
for(int i = 18;i >= 0;i --) {
if(f[a][i] != f[b][i]) {
a = f[a][i],b = f[b][i];
}
}
return f[a][0];
}
signed main() {
n = read();m = read();
for(int i = 1;i < n;i ++) {
s = read();o = read();
g[s].push_back(o);
g[o].push_back(s);
u[i] = s;v[i] = o;
x[i] = read();
}
dfs(1,0);
for(int i = 1;i < n;i ++) if(d[u[i]] < d[v[i]]) swap(u[i],v[i]);
for(int i = 1;i <= m;i ++) {
q[i].k = read();
if(q[i].k == 1) {
q[i].u = read();
q[i].v = read();
q[i].y = read();
}
else {
q[i].u = read();
LL ss = read();
q[i].y = x[q[i].u];
x[q[i].u] = ss;
}
}
maketree(cnt);
addtree(1,cnt,1);
fe[1] = 1ll;
for(int i = 1;i < n;i ++) {
fe[u[i]] = x[i];
if(x[i] > 1) {
addtree(dfn[u[i]],rr[u[i]],u[i]);
}
}
stack<LL> as;
for(int i = m;i > 0;i --) {
if(q[i].k == 2) {
int j = q[i].u;
if(x[j] <= 1ll && q[i].y > 1ll) addtree(dfn[u[j]],rr[u[j]],u[j]);
fe[u[j]] = x[j] = q[i].y;
}
else {
// for(int j = 1;j < n;j ++) printf("%lld ",x[j]);ENDL;
s = q[i].u,o = q[i].v;
LL y = q[i].y;
int lc = lca(s,o);
while(d[s] > d[lc]) {
if(y <= 0) break;
y /= fe[s];
s = findt(dfn[f[s][0]]);
}
stack<LL> no;
LL sum = 1ll;
while(d[o] > d[lc]) {
if(sum > y) break;
sum *= fe[o];
no.push(fe[o]);
o = findt(dfn[f[o][0]]);
}
while(!no.empty()) y /= no.top(),no.pop();
as.push(y);
}
}
while(!as.empty()) printf("%lld\n",as.top()),as.pop();
return 0;
}
