记录编号	391124	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2016 Round1] 游戏	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	3.625 s
提交时间	2017-04-05 09:58:45	内存使用	15.67 MiB

#include <stdio.h>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#define Mem(a, b) memset(a, b, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
#define RG register
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;
IL void qkin(RG int &res){
	RG int x,f=1; RG char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;}
IL void read(RG int &A){ qkin(A); }
IL void read(RG int &A,RG int &B){ qkin(A),qkin(B); }
IL void read(RG int &A,RG int &B,RG int &C){ qkin(A),qkin(B),qkin(C); }
#define Gets(s) scanf("%s", s+1);
const double INF = 1e60;
const LL inf = 123456789123456789ll;
const double Pi = acos(-1);
const double eps = 1e-8;
const int maxn = 100010;

int n, m, len, head[maxn];
struct Edge{
	int to, next, dis;
}e[maxn<<1];
void addEdge(int x,int y,int z){
	e[++len].to = y;
	e[len].dis = z;
	e[len].next = head[x];
	head[x] = len;	
}
LL dis[maxn];
int top[maxn], fa[maxn], size[maxn], son[maxn], deep[maxn];
int cnt, id[maxn], pos[maxn];
bool vis[maxn];
void Dfs1(int x){
	vis[x] = 1; size[x] = 1; son[x] = 0;
	for(int i=head[x]; i; i=e[i].next){
		int p = e[i].to;
		if(!vis[p]){
			deep[p] = deep[x] + 1;
			fa[p] = x;
			dis[p] = dis[x] + e[i].dis;
			Dfs1(p);
			size[x] += size[p];
			if(size[p] > size[son[x]]) son[x] = p;
		}
	}
}
void Dfs2(int x,int tp){
	vis[x] = 1; top[x] = tp; id[x] = ++cnt; pos[cnt] = x;
	if(son[x]) Dfs2(son[x], tp);
	for(int i=head[x]; i; i=e[i].next){
		int p = e[i].to;
		if(!vis[p] && son[x] != p) Dfs2(p, p);
	}
}
int tree_lca(int x,int y){
	int fx = top[x], fy = top[y];
	while(fx != fy){
		if(deep[fx] < deep[fy]) swap(fx, fy), swap(x, y);
		x = fa[fx]; fx = top[x];
	}
	return deep[x] < deep[y] ? x : y;
}
struct node{
	LL k, b;
	node(LL kk = 0, LL bb = inf){
		k = kk; b = bb;
	}
	LL val(int x){
		return k * dis[pos[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;
	}
}T[maxn<<2];

#define lc rt<<1
#define rc rt<<1|1
#define mid (((l) + (r)) >> (1))
#define lson lc, l, mid
#define rson rc, mid+1, r

LL Min[maxn<<2];

void Motify(int s,int t,node Q,int rt,int l,int r){
	int ql = max(s, l), qr = min(r, t);
	Min[rt] = min(Min[rt], min(Q.val(ql), Q.val(qr)));
	if(s<=l && t>=r){
		int tmp = Q.cmp(l, r, T[rt]);
		if(tmp == 1){ T[rt] = Q; return; }
		if(tmp == -1){ return;	}
	}
	if(l == r) return;
	if(s<=mid) Motify(s, t, Q, lson); 
	if(t> mid) Motify(s, t, Q, rson);
}
void tree_motify(int x,int y,node Q){
	int fx = top[x], fy = top[y];
	while(fx != fy){
		if(deep[fx] < deep[fy]) swap(fx, fy), swap(x, y);
		Motify(id[fx], id[x], Q, 1, 1, n);
		x = fa[fx]; fx = top[x];
	}
	if(deep[x] > deep[y]) swap(x, y);
	Motify(id[x], id[y], Q, 1, 1, n);
}
LL query(int s,int t,int rt,int l,int r){
	if(s<=l && t>=r) return Min[rt]; 
	int ql = max(s, l), qr = min(t, r);
	LL res = min( T[rt].val(ql), T[rt].val(qr) );
	if(t<=mid) return min(res, query(s,t,lson));
	if(s> mid) return min(res, query(s,t,rson));
	return min(res, min(query(s,t,lson), query(s,t,rson))); 
}
LL tree_query(int x,int y){
	int fx = top[x], fy = top[y]; LL res = inf;
	while(fx != fy){
		if(deep[fx] < deep[fy]) swap(fx, fy), swap(x, y);
		res = min(res, query(id[fx], id[x], 1, 1, n));
		x = fa[fx]; fx = top[x];
	} 
	if(deep[x] > deep[y]) swap(x, y);
	res = min(res, query(id[x], id[y], 1, 1, n)); 
	return res;
}

int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("menci_game.in","r",stdin);
	freopen("menci_game.out","w",stdout);
#endif
	read(n, m);
	for(int i=1; i<n; i++){
		int x, y, z; read(x, y, z);
		addEdge(x, y, z); addEdge(y, x, z);
	}
	deep[1] = 1; Dfs1(1);
	Mem(vis, 0); Dfs2(1, 1);
	
	for(int i=0; i<maxn*4; i++){
		Min[i] = inf;
	}
	int op, x, y, a, b;
	while( m -- ){
		read(op, x, y);
		if(op == 1){
			read(a, b);
			int lca = tree_lca(x, y);
			node Q = node(-a, dis[x] * a + b);
			tree_motify(x, lca, Q);
			Q = node(a, (dis[x] - 2 * dis[lca]) * a + b);
			tree_motify(lca, y, Q);
		}
		else {
			printf("%lld\n", tree_query(x, y));
		}
	}
	getchar(); getchar();
	return 0;
}