每次修改可以看成是一个一次函数，分成两个点到(lca)分别修改
于是树链剖分+李超线段树+标记永久化求最小值
时间复杂度(O(nlog_n^3))，但出题人良心可以过
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=1e5+4,inf=123456789123456789ll;
#define lc (p<<1)
#define rc (p<<1|1)
int n,m,tim;
int dis[N],dep[N],siz[N],son[N],fa[N],pos[N],dfn[N],top[N];
int tk[N<<2],tb[N<<2],mn[N<<2],lx[N<<2],rx[N<<2],mx[N<<2];
void build(int p,int l,int r){
tb[p]=mn[p]=inf;
lx[p]=dis[pos[l]];rx[p]=dis[pos[r]];
int mid=l+r>>1;
mx[p]=dis[pos[mid]];
if(l==r)return;
build(lc,l,mid);build(rc,mid+1,r);
}
void modify(int p,int l,int r,int ql,int qr,int k,int b){
int mid=l+r>>1;
if(ql<=l&&r<=qr){
int l1=k*lx[p]+b,r1=k*rx[p]+b,l2=tk[p]*lx[p]+tb[p],r2=tk[p]*rx[p]+tb[p];
if(l1>=l2&&r1>=r2)return;
if(l1<l2&&r1<r2){
tk[p]=k;tb[p]=b;
mn[p]=min(mn[p],min(l1,r1));
return;
}
double x=(double)(b-tb[p])/(tk[p]-k);
if(l1>l2){
if(x<=mx[p]){
modify(lc,l,mid,ql,qr,tk[p],tb[p]);
tk[p]=k;tb[p]=b;
}
else modify(rc,mid+1,r,ql,qr,k,b);
}
else{
if(x<=mx[p])modify(lc,l,mid,ql,qr,k,b);
else{
modify(rc,mid+1,r,ql,qr,tk[p],tb[p]);
tk[p]=k;tb[p]=b;
}
}
mn[p]=min(mn[p],min(l1,r1));
return;
}
if(ql<=mid)modify(lc,l,mid,ql,qr,k,b);
if(mid<qr)modify(rc,mid+1,r,ql,qr,k,b);
mn[p]=min(mn[p],min(mn[lc],mn[rc]));
}
inline int query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return mn[p];
int mid=l+r>>1,xl=max(l,ql),xr=min(r,qr);
int ret=min(dis[pos[xl]]*tk[p],dis[pos[xr]]*tk[p])+tb[p];
if(ql<=mid)ret=min(ret,query(lc,l,mid,ql,qr));
if(mid<qr)ret=min(ret,query(rc,mid+1,r,ql,qr));
return ret;
}
struct edge{
int v,w,nxt;
}e[N<<1];
int first[N],cnt=0;
inline void add(int u,int v,int w){
e[++cnt]=(edge){v,w,first[u]};
first[u]=cnt;
}
void dfs_1(int x){
dep[x]=dep[fa[x]]+1;
siz[x]=1;
for(int i=first[x],v;i;i=e[i].nxt){
v=e[i].v;
if(v==fa[x])continue;
fa[v]=x;
dis[v]=dis[x]+e[i].w;
dfs_1(v);
siz[x]+=siz[v];
if(siz[v]>siz[son[x]])son[x]=v;
}
}
void dfs_2(int x,int tp){
top[x]=tp;
dfn[x]=++tim;
pos[tim]=x;
if(son[x]){
dfs_2(son[x],tp);
}
for(int i=first[x],v;i;i=e[i].nxt){
v=e[i].v;
if(v==son[x]||v==fa[x])continue;
dfs_2(v,v);
}
}
inline int LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])u^=v^=u^=v;
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
inline int query(int u,int v){
int ret=inf;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])u^=v^=u^=v;
ret=min(ret,query(1,1,n,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(dep[u]>dep[v])u^=v^=u^=v;
return min(ret,query(1,1,n,dfn[u],dfn[v]));
}
inline void modify(int u,int v,int k,int b){
while(top[u]!=top[v]){
modify(1,1,n,dfn[top[u]],dfn[u],k,b);
u=fa[top[u]];
}
modify(1,1,n,dfn[v],dfn[u],k,b);
}
signed main(){
n=read();m=read();
for(int i=1,u,v,w;i<n;i++){
u=read();v=read();w=read();
add(u,v,w);add(v,u,w);
}
dfs_1(1);
dfs_2(1,1);
build(1,1,n);
while(m--){
static int op,u,v,x,y,w;
op=read();u=read();v=read();
if(op==2){cout<<query(u,v)<<"
";continue;}
x=read();y=read();
w=LCA(u,v);
modify(u,w,-x,x*dis[u]+y);
modify(v,w,x,x*(dis[u]-dis[w]*2)+y);
}
return (0-0);
}