记录编号	376614	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2016 Round1] 游戏	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	8.227 s
提交时间	2017-02-27 18:23:47	内存使用	48.13 MiB

//BZOJ 4515
//by Cydiater
//2017.2.27
#include <bits/stdc++.h>
using namespace std;
#define ll 		long long
#define db		double
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)
#define FILE		"menci_game"
const int MAXN=2e5+5;
const ll oo=123456789123456789LL;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int LINK[MAXN],len=0,dep[MAXN],fa[MAXN][25],siz[MAXN],son[MAXN],dfn[MAXN],Pos[MAXN],dfs_clock=0,N,M,top[MAXN];
ll dis[MAXN];
struct edge{
	int y,next;
	ll v;
}e[MAXN<<1];
namespace SegmentTree{
	struct tree{
		ll k,b,val;
		tree(){k=b=-oo;val=oo;}
	}t[MAXN<<2];
	ll col(ll x,ll k,ll b){return x*k+b;}
	void reload(int k){cmin(t[k].val,min(t[k<<1].val,t[k<<1|1].val));}
	void Modify(int leftt,int rightt,int k,int L,int R,ll K,ll B){
		int mid=(leftt+rightt)>>1;
		if(leftt>=L&&rightt<=R){
			cmin(t[k].val,min(col(dis[dfn[leftt]],K,B),col(dis[dfn[rightt]],K,B)));
			if(t[k].k==t[k].b&&t[k].k==-oo){
				t[k].k=K;t[k].b=B;
			}else{
				ll Y1=col(dis[dfn[leftt]],K,B),Y2=col(dis[dfn[rightt]],K,B);
				ll Y3=col(dis[dfn[leftt]],t[k].k,t[k].b),Y4=col(dis[dfn[rightt]],t[k].k,t[k].b);
				if(Y1>=Y3&&Y2>=Y4)return;
				if(Y1<=Y3&&Y2<=Y4){
					t[k].k=K;t[k].b=B;
				}else{
					db pos=1.0*(B-t[k].b)/(1.0*(t[k].k-K));
					if(K>t[k].k){
						Modify(leftt,mid,k<<1,L,R,K,B);
						if(pos>=dis[dfn[mid+1]])Modify(mid+1,rightt,k<<1|1,L,R,K,B);
					}else{
						Modify(mid+1,rightt,k<<1|1,L,R,K,B);
						if(pos<=dis[dfn[mid]])Modify(leftt,mid,k<<1,L,R,K,B);
					}
				}
			}
			reload(k);
			return;
		}
		if(mid>=L)	Modify(leftt,mid,k<<1,L,R,K,B);
		if(mid+1<=R)	Modify(mid+1,rightt,k<<1|1,L,R,K,B);
		reload(k);
	}
	ll Query(int leftt,int rightt,int k,int L,int R){
		ll ans=oo;
		if(t[k].k!=-oo){
			cmin(ans,col(dis[dfn[max(L,leftt)]],t[k].k,t[k].b));
			cmin(ans,col(dis[dfn[min(R,rightt)]],t[k].k,t[k].b));
		}
		int mid=(leftt+rightt)>>1;
		if(leftt>=L&&rightt<=R){
			cmin(ans,t[k].val);
			return ans;
		}
		if(mid>=L)	cmin(ans,Query(leftt,mid,k<<1,L,R));
		if(mid+1<=R)	cmin(ans,Query(mid+1,rightt,k<<1|1,L,R));
		return ans;
	}
}
namespace solution{
	inline void insert(int x,int y,ll v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
	inline void Insert(int x,int y,ll v){insert(x,y,v);insert(y,x,v);}
	void Get_Anc(){
		up(i,1,20)up(node,1,N)if(fa[node][i-1])
			fa[node][i]=fa[fa[node][i-1]][i-1];
	}
	int LCA(int x,int y){
		if(x==y)	return x;
		if(dep[x]<dep[y])swap(x,y);
		down(i,20,0)if(dep[x]-(1<<i)>=dep[y])
			x=fa[x][i];
		if(x==y)	return x;
		down(i,20,0)if(fa[x][i]!=fa[y][i]&&fa[x][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
		return fa[x][0];
	}
	void DFS1(int node,int deep,int father){
		dep[node]=deep;fa[node][0]=father;siz[node]=1;
		Auto(i,node)if(e[i].y!=father){
			dis[e[i].y]=dis[node]+e[i].v;
			DFS1(e[i].y,deep+1,node);
			siz[node]+=siz[e[i].y];
			if(siz[e[i].y]>siz[son[node]])son[node]=e[i].y;
		}
	}
	void DFS2(int node,int TOP){
		top[node]=TOP;dfn[++dfs_clock]=node;
		Pos[node]=dfs_clock;
		if(son[node])DFS2(son[node],TOP);
		Auto(i,node)if(e[i].y!=fa[node][0]&&e[i].y!=son[node])
			DFS2(e[i].y,e[i].y);
	}
	void Modify(int now,int aim,ll k,ll b){
		while(top[now]!=top[aim]){
			int L=Pos[top[now]],R=Pos[now];
			SegmentTree::Modify(1,N,1,L,R,k,b);
			now=fa[top[now]][0];
		}
		int L=Pos[aim],R=Pos[now];
		SegmentTree::Modify(1,N,1,L,R,k,b);
	}
	ll Query(int now,int aim){
		ll ans=oo;
		while(top[now]!=top[aim]){
			int L=Pos[top[now]],R=Pos[now];
			cmin(ans,SegmentTree::Query(1,N,1,L,R));
			now=fa[top[now]][0];
		}
		int L=Pos[aim],R=Pos[now];
		cmin(ans,SegmentTree::Query(1,N,1,L,R));
		return ans;
	}
	void Prepare(){
		N=read();M=read();
		up(i,2,N){
			int x=read(),y=read(),v=read();
			Insert(x,y,v);
		}
		DFS1(1,0,0);
		DFS2(1,1);
		Get_Anc();
	}
	void Solve(){
		while(M--){
			int op=read();
			if(op==1){
				int x=read(),y=read(),a=read(),b=read(),lca=LCA(x,y);
				Modify(x,lca,-a,b+a*dis[x]);
				Modify(y,lca,a,b-2*a*dis[lca]+a*dis[x]);
			}else{
				int x=read(),y=read(),lca=LCA(x,y);
				printf("%lld\n",min(Query(x,lca),Query(y,lca)));
			}
		}
	}
}
int main(){
	//freopen("input.in","r",stdin);
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}