看到这种题，想都不用想，先写一个树链剖分
然后发现修改操作增加的是等差数列，这使我们想到了李超线段树
先进性树剖，然后用李超线段树维护区间最小，这样就做完了（写码很容易出错）
复杂度为\(O(n\log^3n)\)，少见的复杂度啊qaq，但常数不用怕
#include <bits/stdc++.h>
#define ll long long
#define N 100005
#define M 100005
#define inf 123456789123456789LL
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read()
{
register ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register ll x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[25];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline ll Min(register ll a,register ll b)
{
return a<b?a:b;
}
struct edge{
int to,next;
ll v;
}e[M<<1];
int head[N],cnt=0;
inline void add(register int u,register int v,register ll w)
{
e[++cnt]=(edge){v,head[u],w};
head[u]=cnt;
}
inline ll f(register ll x,register ll k,register ll b)
{
return x*k+b;
}
struct node{
ll a,b,minn;
}tr[N<<2];
int n,m;
int size[N],fa[N],son[N],dep[N];
int pl[N],top[N],tot=0;
ll dis[N],pre[N];
inline void build(register int x,register int l,register int r)
{
tr[x].a=0,tr[x].b=tr[x].minn=inf;
if(l==r)
return;
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
inline void dfs1(register int x)
{
size[x]=1;
for(register int i=head[x];i;i=e[i].next)
if(e[i].to!=fa[x])
{
fa[e[i].to]=x;
dep[e[i].to]=dep[x]+1;
dis[e[i].to]=dis[x]+e[i].v;
dfs1(e[i].to);
if(size[e[i].to]>size[son[x]])
son[x]=e[i].to;
size[x]+=size[e[i].to];
}
}
inline void dfs2(register int x,register int t)
{
pl[x]=++tot,pre[tot]=dis[x],top[x]=t;
if(son[x])
dfs2(son[x],t);
for(register int i=head[x];i;i=e[i].next)
if(e[i].to!=son[x]&&e[i].to!=fa[x])
dfs2(e[i].to,e[i].to);
}
inline int getlca(register int x,register int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
x^=y^=x^=y;
x=fa[top[x]];
}
if(dep[x]>dep[y])
x^=y^=x^=y;
return x;
}
inline void Change(register int x,register int l,register int r,register ll a,register ll b)
{
int mid=l+r>>1,fl,fr,fm;
fl=(f(pre[l],tr[x].a,tr[x].b)>f(pre[l],a,b));
fr=(f(pre[r],tr[x].a,tr[x].b)>f(pre[r],a,b));
fm=(f(pre[mid],tr[x].a,tr[x].b)>f(pre[mid],a,b));
if(fl&&fr&&fm)
{
tr[x].a=a,tr[x].b=b,tr[x].minn=Min(tr[x].minn,Min(f(pre[l],a,b),f(pre[r],a,b)));
return;
}
if(!(fl|fr|fm))
return;
if(fm)
{
if(fr)
Change(x<<1,l,mid,tr[x].a,tr[x].b);
else
Change(x<<1|1,mid+1,r,tr[x].a,tr[x].b);
tr[x].a=a,tr[x].b=b,tr[x].minn=Min(tr[x].minn,Min(f(pre[l],a,b),f(pre[r],a,b)));
}
else
{
if(!fr)
Change(x<<1,l,mid,a,b);
else
Change(x<<1|1,mid+1,r,a,b);
}
tr[x].minn=Min(tr[x].minn,Min(tr[x<<1].minn,tr[x<<1|1].minn));
}
inline void change(register int x,register int l,register int r,register int L,register int R,register ll a,register ll b)
{
if(L<=l&&r<=R)
{
Change(x,l,r,a,b);
return;
}
int mid=l+r>>1;
if(L<=mid)
change(x<<1,l,mid,L,R,a,b);
if(R>mid)
change(x<<1|1,mid+1,r,L,R,a,b);
tr[x].minn=Min(tr[x].minn,Min(tr[x<<1].minn,tr[x<<1|1].minn));
}
inline void cal1(register int s,register int t,register ll a,register ll b)
{
int lca=getlca(s,t);
int x=s,y=t;
while(top[x]!=top[lca])
{
change(1,1,n,pl[top[x]],pl[x],-a,a*dis[s]+b);
x=fa[top[x]];
}
change(1,1,n,pl[lca],pl[x],-a,a*dis[s]+b);
while(top[y]!=top[lca])
{
change(1,1,n,pl[top[y]],pl[y],a,dis[s]*a-dis[lca]*2*a+b);
y=fa[top[y]];
}
if(y!=lca)
change(1,1,n,pl[lca]+1,pl[y],a,dis[s]*a-dis[lca]*2*a+b);
}
inline ll query(register int x,register int l,register int r,register int L,register int R)
{
ll res=Min(f(pre[L],tr[x].a,tr[x].b),f(pre[R],tr[x].a,tr[x].b));
if(L==l&&r==R)
return Min(res,tr[x].minn);
int mid=l+r>>1;
if(R<=mid)
return Min(res,query(x<<1,l,mid,L,R));
else if(L>mid)
return Min(res,query(x<<1|1,mid+1,r,L,R));
else
return Min(res,Min(query(x<<1,l,mid,L,mid),query(x<<1|1,mid+1,r,mid+1,R)));
}
inline ll cal2(register int s,register int t)
{
int x=s,y=t;
ll res=inf;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
x^=y^=x^=y;
res=Min(res,query(1,1,n,pl[top[x]],pl[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])
x^=y^=x^=y;
res=Min(res,query(1,1,n,pl[x],pl[y]));
return res;
}
int main()
{
n=read(),m=read();
for(register int i=1;i<=n-1;++i)
{
int u=read(),v=read();
ll w=read();
add(u,v,w),add(v,u,w);
}
dfs1(1);
dfs2(1,1);
build(1,1,n);
while(m--)
{
int opt=read();
if(opt==1)
{
int s=read(),t=read();
ll a=read(),b=read();
cal1(s,t,a,b);
}
else
{
int s=read(),t=read();
write(cal2(s,t)),puts("");
}
}
return 0;
}
