题面

题解

我们发现，对于除法有效的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;
}