RT，wzbl /kk

不知道 MAX 要开多大

#include <bits/stdc++.h>
#define ll long long
#define ls(x) tree[x].son[0]
#define rs(x) tree[x].son[1]
#define l(x) tree[x].l
#define w(x) tree[x].w
#define Mid ((L+R)>>1)
using namespace std;
typedef pair<int,int> pii;
inline int read(){
	char c;int x=0;int b=1;do{c=getchar();if(c==45)b=-1;}while(c>57||c<48);
	do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);x*=b;return x;
}
const int maxn=100010;
const ll MAX=1e15,inf=123456789123456789ll;
namespace LiChao_tree{
	struct line{
		ll k,b;
		ll calc(ll x){return k*x+b;}
	};const line lmax={0ll,inf};
	struct tree{
		int son[2];
		ll w;line l;
	}tree[maxn*100];int cnt,root;
	ll getmin(line l,ll L,ll R){
		return min(l.calc(L),l.calc(R));
	}
	void update(int root,ll L,ll R){
		w(root)=getmin(l(root),L,R);
		if(ls(root))w(root)=min(w(root),w(ls(root)));
		if(rs(root))w(root)=min(w(root),w(rs(root)));
	}
	void add(int &root,ll L,ll R,ll l,ll r,line g){
		if(!root)root=++cnt,l(root)=lmax;
		if(L==l && R==r){
			if(l(root).calc(Mid)>g.calc(Mid))swap(l(root),g);
			if(l(root).k>g.k)add(rs(root),Mid+1,R,Mid+1,r,g);
			else if(l(root).k<g.k)add(ls(root),L,Mid,l,Mid,g);
			update(root,L,R);
		}else{
			if(r<=Mid)add(ls(root),L,Mid,l,r,g);
			else if(l>Mid)add(rs(root),Mid+1,R,l,r,g);
			else add(ls(root),L,Mid,l,Mid,g),add(rs(root),Mid+1,R,Mid+1,r,g);
			update(root,L,R);
		}
	}
	ll find(int root,ll L,ll R,ll l,ll r){
		if(!root)return inf;
		ll ans=getmin(l(root),l,r);
		if(L==l && R==r)return w(root);
		if(r<=Mid)return min(ans,find(ls(root),L,Mid,l,r));
		else if(l>Mid)return min(ans,find(rs(root),Mid+1,R,l,r));
		else return min(ans,min(find(ls(root),L,Mid,l,Mid),find(rs(root),Mid+1,R,Mid+1,r)));
	}
}using namespace LiChao_tree;
struct edge{
	int next,to,w;
}a[maxn*2];
int head[maxn],len;
void add(int x,int y,int z){
	a[++len]={head[x],y,z};
	head[x]=len;
}int i,j,k,n,m,size[maxn],h[maxn],dfn[maxn],D,top[maxn],F[maxn],deep[maxn],Root[maxn];
ll Deep[maxn];
void dfs(int now,int fa){
	size[now]=1;deep[now]=deep[fa]+1;F[now]=fa;
	for(int i=head[now];i;i=a[i].next){
		int u=a[i].to;
		if(u==fa)continue;
		Deep[u]=Deep[now]+a[i].w;
		dfs(u,now);size[now]+=size[u];
		if(size[u]>size[h[now]])h[now]=u;
	}
}
void dfs2(int now,int fa,int tp){
	top[now]=tp;dfn[now]=++D;
	if(h[now])dfs2(h[now],now,tp);
	for(int i=head[now];i;i=a[i].next){
		int u=a[i].to;
		if(u==fa || u==h[now])continue;
		dfs2(u,now,u);
	}
}
inline int lca(int x,int y){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		x=F[top[x]];
	}return dfn[x]<dfn[y]?x:y;
}
inline ll dist(int x,int y){
	return Deep[x]+Deep[y]-2*Deep[lca(x,y)];
}
line getline(ll x1,ll y1,ll x2,ll y2){
	//cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;
	if(x1==x2)return (line){0ll,y1};
	ll k=(y2-y1)/(x2-x1);ll b=y1-x1*k;
	return (line){k,b};
}
void insert(int x,int y,ll a,ll b){
	//cerr<<Deep[x]<<' '<<Deep[y]<<endl;
	int S=x;
	//cout<<"insert "<<x<<' '<<y<<' '<<a<<' '<<b<<endl;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		//cout<<"Insert "<<top[x]<<' '<<x<<endl;
		add(Root[top[x]],1,MAX,Deep[top[x]],Deep[x],getline(Deep[top[x]],b+dist(top[x],S)*a,Deep[x],b+dist(x,S)*a));
		x=F[top[x]];
	}if(dfn[x]<dfn[y])swap(x,y);
	//cout<<"Insert "<<y<<' '<<Deep[y]<<' '<<x<<' '<<Deep[x]<<endl;
	add(Root[top[x]],1,MAX,Deep[y],Deep[x],getline(Deep[y],b+dist(y,S)*a,Deep[x],b+dist(x,S)*a));
}
ll check(int x,int y){
	ll ans=123456789123456789ll;
	//cout<<"checking "<<x<<' '<<y<<endl;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		ans=min(ans,find(Root[top[x]],1,MAX,Deep[top[x]],Deep[x]));
		//cout<<"check "<<top[x]<<' '<<x<<' '<<ans<<endl;
		x=F[top[x]];
	}if(dfn[x]<dfn[y])swap(x,y);
	ans=min(ans,find(Root[top[x]],1,MAX,Deep[y],Deep[x]));
	//cout<<"check "<<y<<' '<<x<<' '<<ans<<endl;
	//cout<<"!"<<find(Root[top[2]],1,MAX,Deep[2],Deep[2])<<endl;
	return ans;
}
signed main() {
	freopen("P4069.in","r",stdin);
	freopen("P4069.out","w",stdout);
	cin>>n>>m;
	for(i=1;i<n;i++){
		int x=read(),y=read(),z=read();
		add(x,y,z);add(y,x,z);
	}Deep[1]=1;
	dfs(1,0);dfs2(1,0,1);
	for(i=1;i<=m;i++){
		//cerr<<i<<" OK!"<<endl;
		int op=read();
		if(op==1){
			int s=read(),t=read();ll a=read(),b=read();
			insert(s,t,a,b);
		}else{
			int s=read(),t=read();
			printf("%lld\n",check(s,t));
		}
	}
	cerr << 1.0*clock()/CLOCKS_PER_SEC << endl;
	return 0;
}