记录编号	268240	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2016 Round1] 游戏	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	6.847 s
提交时间	2016-06-12 11:58:54	内存使用	15.57 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=100010;
const long long INF=123456789123456789LL;
int n,Q,cnt;
int fir[maxn],nxt[maxn<<1],to[maxn<<1],val[maxn<<1];
int dep[maxn],fa[maxn],sz[maxn],son[maxn];
long long dis[maxn];
void addedge(int a,int b,int v){
	nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;val[cnt]=v;
}

void DFS(int x){
	sz[x]=1;
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa[x]){
			fa[to[i]]=x;
			dis[to[i]]=dis[x]+val[i];
			dep[to[i]]=dep[x]+1;
			DFS(to[i]);
			sz[x]+=sz[to[i]];
			if(sz[son[x]]<sz[to[i]])
				son[x]=to[i];	
		}	
}

int top[maxn],ID[maxn],rID[maxn],tot;
void DFS(int x,int tp){
	ID[x]=++tot;rID[tot]=x;top[x]=tp;
	if(son[x])DFS(son[x],tp);
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=son[x]&&to[i]!=fa[x])
			DFS(to[i],to[i]);	
}

int Lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}

struct Node{
	long long a,b;
	Node(long long a_=0,long long b_=INF){
		a=a_;b=b_;
	}
	long long Val(int x){
		return a*dis[rID[x]]+b;
	}
	int CmP(int l,int r,Node a){
		if(Val(l)<=a.Val(l)&&Val(r)<=a.Val(r))return 1;
		if(Val(l)>=a.Val(l)&&Val(r)>=a.Val(r))return -1;
		return 0;	
	}
}F[maxn<<2];
long long Min[maxn<<2];

void Build(int x,int l,int r){
	Min[x]=INF;
	if(l==r)return;
	Build(x<<1,l,(l+r)>>1);
	Build(x<<1|1,((l+r)>>1)+1,r);
}

void Update(int x,int l,int r,int a,int b,Node p){
	int mid=(l+r)>>1;
	Min[x]=min(Min[x],min(p.Val(max(a,l)),p.Val(min(b,r))));
	if(l>=a&&r<=b){
		int tmp=p.CmP(l,r,F[x]);
		if(tmp==1)F[x]=p;
		if(tmp!=0)return;
		
		tmp=p.CmP(l,mid,F[x]);
		if(tmp!=1)Update(x<<1,l,mid,a,b,F[x]);
		
		tmp=p.CmP(mid+1,r,F[x]);
		if(tmp!=1)Update(x<<1|1,mid+1,r,a,b,F[x]);
	}
	if(l==r)return;
	if(mid>=a)Update(x<<1,l,mid,a,b,p);
	if(mid<b)Update(x<<1|1,mid+1,r,a,b,p);
}

void Modify(int x,int y,Node p){
	while(top[x]!=top[y]){
		Update(1,1,n,ID[top[x]],ID[x],p);
		x=fa[top[x]];
	}
	Update(1,1,n,ID[y],ID[x],p);
}

long long Query(int x,int l,int r,int a,int b){
	if(l>=a&&r<=b)return Min[x];
	int mid=(l+r)>>1;
	long long ret=min(F[x].Val(max(l,a)),F[x].Val(min(r,b)));
	if(mid>=a)ret=min(ret,Query(x<<1,l,mid,a,b));
	if(mid<b)ret=min(ret,Query(x<<1|1,mid+1,r,a,b));
	return ret;
}

long long Solve(int x,int y){
	long long ret=INF;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ret=min(ret,Query(1,1,n,ID[top[x]],ID[x]));
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	return min(ret,Query(1,1,n,ID[y],ID[x]));
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("menci_game.in","r",stdin);
	freopen("menci_game.out","w",stdout);
#endif
	scanf("%d%d",&n,&Q);
	for(int i=1,x,y,w;i<n;i++){
		scanf("%d%d%d",&x,&y,&w);
		addedge(x,y,w);addedge(y,x,w);
	}
	
	DFS(1);
	DFS(1,1);
	Build(1,1,n);
	
	int type,s,t,lca;
	long long a,b;
	while(Q--){
		scanf("%d",&type);
		if(type==1){
			scanf("%d%d%lld%lld",&s,&t,&a,&b);
			lca=Lca(s,t);
			Modify(s,lca,Node(-a,a*dis[s]+b));
			Modify(t,lca,Node(a,a*(dis[s]-2*dis[lca])+b));
		}
		else{
			scanf("%d%d",&s,&t);
			printf("%lld\n",Solve(s,t));
		}
	}
	return 0;
}