593D - Happy Tree Party - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int lim = 1000000000000000001ll;
int f[400005],siz[400005],top[400005],dep[400005],id[400005],dfsn[400005],val[400005],son[400005];
int tot=0;
vector<pair<int,int> > v[600005];
struct tmp{
    int x,y;
}s[400005];
int solve(int x, int y) {
    int z;
    if(x>lim/y) z=lim;
    else z=x*y;
    return z;
}
struct segment_tree{
    struct node{
        int l,r,sum;
    }tree[4*200005];
     void push_up(int p){
     	tree[p].sum=solve(tree[p<<1].sum,tree[p<<1|1].sum);
    }
	void build(int l,int r,int p){
        tree[p].l=l;
        tree[p].r=r;
        tree[p].sum=1;
        if(l==r){
            tree[p].sum=val[id[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,p<<1);
        build(mid+1,r,p<<1|1);
        push_up(p);
    }
    void change(int x,int p,int c){
        if(tree[p].l==tree[p].r){
            tree[p].sum=c;
            return;
        }
        int mid=(tree[p].l+tree[p].r)>>1;
        if(x<=mid)change(x,p<<1,c);
        else change(x,p<<1|1,c);
        push_up(p);
    }
    int query(int l,int r,int p){
        if(tree[p].l==l&&tree[p].r==r){
            return tree[p].sum;
        }
        int mid=(tree[p].l+tree[p].r)>>1;
        if(r<=mid)return query(l,r,p<<1);
        else if(l>mid)return query(l,r,p<<1|1);
        else return solve(query(l,mid,p<<1),query(mid+1,r,p<<1|1));
    }
}seg;
void dfs(int x,int fa){
    f[x]=fa;
    dep[x]=dep[fa]+1;
    siz[x]=1;
    for(int i=0;i<v[x].size();i++){
        int to=v[x][i].first,w=v[x][i].second;
        if(to==fa)continue;
        dfs(to,x);
        val[to]=w;
        siz[x]+=siz[to];
        if(siz[to]>siz[son[x]]){
            son[x]=to;
        }
    }
}
void redfs(int x,int fa,int tp){
    dfsn[x]=++tot;
    id[tot]=x;
    top[x]=tp;
    if(son[x])redfs(son[x],x,tp);
    for(int i=0;i<v[x].size();i++){
        int to=v[x][i].first;
        if(to==fa||to==son[x])continue;
        redfs(to,x,to);
    }
}
int q(int x,int y){
    long double res=1;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]){
            swap(x,y);
        }
        res=solve(res,seg.query(dfsn[top[x]],dfsn[x],1));
        x=f[top[x]];
    }
    if(x==y)return res;
    if(dep[x]<dep[y])swap(x,y);
    res=solve(res,seg.query(dfsn[y]+1,dfsn[x],1));
    return res;
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        s[i].x=a;
        s[i].y=b;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    dfs(1,0);
    redfs(1,0,1);    
    seg.build(1,n,1);
    for(int i=1;i<=m;i++){
        int op,a,b,c,p;
        cin>>op;
        if(op==1){
            cin>>a>>b>>c;
            cout<<c/q(a,b)<<endl;
        }
        else{
            cin>>p>>c;
            int a=s[p].x,b=s[p].y;
            if(f[a]==b)swap(a,b);
            seg.change(dfsn[b],1,c);
        }
    }
 
    return 0;
}