记录编号	391094	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2222.[SDOI 2016 Round1] 游戏	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	3.593 s
提交时间	2017-04-05 09:02:37	内存使用	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], son[maxn], size[maxn], deep[maxn];
int id[maxn], pos[maxn], cnt;
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[son[x]] < size[p]) 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);
	}
}

struct node{
	LL k, b;
	node(LL _k = 0,LL _b = inf){
		k = _k; b = _b;
	}
	LL val(int x){
		return k * dis[pos[x]] + b;
	}
	int cmp(int l,int r,node B){
		if(val(l)<=B.val(l) && val(r)<=B.val(r)) return 1;
		if(val(l)>=B.val(l) && val(r)>=B.val(r)) return -1;
		return 0;
	}
}a[maxn<<2], b;

LL Min[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


void build(int rt, int l, int r){
	Min[rt] = inf;
	if(l == r) return;
	build(lson); build(rson);
}

void print_tree(){
	for(int i=1; i<=n; i++){
		printf("i->%d  fa = %d  top = %d  id = %d  dis = %d\n", 
			i, fa[i], top[i], id[i], dis[i]);
	}
}
int tree_lca(int x,int y){
	int fx = top[x], fy = top[y];
	while(fx != fy){
		if(deep[fx] < deep[fy]) { swap(x, y); swap(fx, fy);	}
		x = fa[fx]; fx = top[x];
	}
	return deep[x]<deep[y] ? x : y;
}
void Motify(int s,int t,int rt,int l,int r){
	int ql = max(l, s), qr = min(r, t);
	Min[rt] = min(Min[rt], min(b.val(ql), b.val(qr)));
	if(s<=l && t>=r){
		int tmp = b.cmp(l, r, a[rt]);
		if(tmp == 1) { a[rt] = b; return; }
		if(tmp == -1) return;
		
		tmp = b.cmp(l, mid, a[rt]);
		if(tmp!=1) Motify(s, t, lson);
		
		tmp = b.cmp(mid+1, 1, a[rt]);
		if(tmp!=1) Motify(s, t, rson);
	}
	if(l == r) return;
	if(s<=mid) Motify(s, t, lson);
	if(t> mid) Motify(s, t, rson);
}
void tree_motify(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); }
		Motify(id[fx], id[x], 1, 1, n);
		x = fa[fx]; fx = top[x];
	}
	if(deep[x] > deep[y]) swap(x, y);
	Motify(id[x], id[y], 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(a[rt].val(ql), a[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(min(res, 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); int x, y, z;
	for(int i=1; i<n; i++)	{
		read(x, y, z); addEdge(x, y, z); addEdge(y, x, z);
	}
	deep[1] = 1; Dfs1(1);
	Mem(vis, 0); Dfs2(1, 1);
	
	//print_tree();
	
	build(1, 1, n);
	
	int op, A, B;
	while(m -- ){
		read(op, x, y);
		if(op == 1){
			read(A, B);
			int lca = tree_lca(x, y);
			b = node(-A, A * dis[x] + B);
			tree_motify(x, lca);
			b = node(A, A*(dis[x] - 2 * dis[lca])+ B);
			tree_motify(lca, y);
		} else {
			LL ans = tree_query(x, y);
			printf("%lld\n", ans);
		}
	}
	
	getchar(); getchar();
	return 0;
}