答案应该是对的啊。。

就是不知道为啥 MLE 了

没超时

#include<bits/stdc++.h>
#define re register int
#define ll long long
#define il inline
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N=2e5+5;
const ll INF=123456789123456789ll;
int n,m,tot,h[N],T,t[N<<2];
int cnt,fa[N],dep[N],siz[N],hs[N],w[N],top[N],pos[N];
ll k[N<<2],b[N<<2],mi[N<<2],dis[N];
struct Edge
{
	int nxt,to,w;
}e[N<<1];
il int read()
{
	re x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
il void add(re x,re y,re w)
{
	e[++T]=(Edge){h[x],y,w};
	h[x]=T;
	e[++T]=(Edge){h[y],x,w};
	h[y]=T;
}
void build(re u,re l,re r)
{
	mi[u]=INF;
	t[u]=1;
	if(l==r) return;
	re mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
il ll calc(re u,re x)
{
	return k[u]*dis[pos[x]]+b[u];
}
il void push_up(re u)
{
	mi[u]=min(mi[u],min(mi[ls],mi[rs]));
}
il void update(re u,re l,re r,re x,re y,re p)
{
	if(y<l||r<x) return;
	re mid=(l+r)>>1;
	if(x<=l&&r<=y)
	{
		if(calc(p,l)<=calc(t[u],l)&&calc(p,r)<=calc(t[u],r))
		{
			t[u]=p;
			mi[u]=min(mi[u],min(calc(p,l),calc(p,r)));
			return;
		}
		if(calc(p,l)>=calc(t[u],l)&&calc(p,r)>=calc(t[u],r)) return;
		if(k[p]<k[t[u]])
		{
			if(calc(p,mid)<=calc(t[u],mid)) update(ls,l,mid,x,y,t[u]),t[u]=p;
				else update(rs,mid+1,r,x,y,p);
		}
		else
		{
			if(calc(p,mid)<=calc(t[u],mid)) update(rs,mid+1,r,x,y,t[u]),t[u]=p;
				else update(ls,l,mid,x,y,p);
		}
		mi[u]=min(mi[u],min(calc(p,l),calc(p,r)));
		push_up(u);
		return;
	}
	if(x<=mid) update(ls,l,mid,x,y,p);
	if(y>mid) update(rs,mid+1,r,x,y,p);
	push_up(u);
}
il ll query(re u,re l,re r,re x,re y)
{
	if(x<=l&&r<=y) return mi[u];
	re mid=(l+r)>>1;
	ll res=INF;
	if(b[t[u]]^INF) res=min(calc(t[u],max(x,l)),calc(t[u],min(y,r)));
	if(x<=mid) res=min(res,query(ls,l,mid,x,y));
	if(y>mid) res=min(res,query(rs,mid+1,r,x,y));
	return res;
}
void dfs1(re u,re fath)
{
	fa[u]=fath;
	dep[u]=dep[fath]+1;
	siz[u]=1;
	hs[u]=-1;
	for(re i=h[u],v;v=e[i].to,i;i=e[i].nxt)
	{
		if(v==fath) continue;
		dis[v]=dis[u]+e[i].w;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(hs[u]==-1||siz[v]>siz[hs[u]]) hs[u]=v;
	}
}
void dfs2(re u,re t)
{
	top[u]=t;
	w[u]=++cnt;
	pos[cnt]=u;
	if(hs[u]!=-1) dfs2(hs[u],t);
	for(re i=h[u],v;v=e[i].to,i;i=e[i].nxt)
		if(v!=hs[u]&&fa[u]!=v)
			dfs2(t,t);
}
il int LCA(re u,re v)
{
	while(top[u]^top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	return v;
}
il void modify(re u,re v)
{
	while(top[u]^top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		update(1,1,n,w[top[u]],w[u],tot);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	update(1,1,n,w[v],w[u],tot);
}
il ll query(re u,re v)
{
	ll ans=INF;
	while(top[u]^top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ans=min(ans,query(1,1,n,w[top[u]],w[u]));
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	ans=min(ans,query(1,1,n,w[v],w[u]));
	return ans;
}
int main()
{
	n=read(),m=read();
	for(re i=1;i<n;i++)
	{
		re u=read(),v=read(),w=read();
		add(u,v,w);
	}
	dfs1(1,0);
	dfs2(1,1);
	k[++tot]=0,b[tot]=INF;
	build(1,1,n);
	while(m--)
	{
		re opt=read(),s=read(),t=read(),x,y,lca=LCA(s,t);
		if(opt&1)
		{
			x=read(),y=read();
			k[++tot]=-x,b[tot]=x*dis[s]+y;
			modify(s,lca);
			k[++tot]=x,b[tot]=x*(dis[s]-(dis[lca]<<1))+y;
			modify(t,lca);
		}
		else printf("%lld\n",query(s,t));
	}
	return 0;
}