C++11(clang++ 3.9) 解法, 执行用时: 551ms, 内存消耗: 25364K, 提交时间: 2020-06-29 17:11:34

#include <bits/stdc++.h>
using namespace std;

#define ll long long

inline int read() {
	char c = getchar(); int x = 0, f = 1;
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

inline void chkmin(ll &x, ll y) { x = x < y ? x : y; }

const int MAXN = 1e5 + 5;
const ll INFLL = 123456789123456789;

ll k[MAXN << 1], b[MAXN << 1], dis[MAXN]; int bl[MAXN];

struct LiChaoTree {
	
	#define ls rt << 1
	#define rs rt << 1 | 1
	
	int t[MAXN << 2]; ll Mn[MAXN << 2];
	
	inline void Init() { t[0] = 1; Mn[0] = INFLL; }
	inline void update(int rt) { Mn[rt] = min(Mn[rt], min(Mn[ls], Mn[rs])); }
	inline ll calc(int x, int id) { return k[id] * (ll)dis[bl[x]] + b[id]; }
	inline void build(int rt, int l, int r) {
		t[rt] = 1; Mn[rt] = INFLL;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(ls, l, mid); build(rs, mid + 1, r);
		update(rt);
	}
	inline void insert(int rt, int l, int r, int L, int R, int id) {
		int mid = (l + r) >> 1;
		if (L <= l && r <= R) {
			if (calc(l, id) <= calc(l, t[rt]) && calc(r, id) <= calc(r, t[rt])) {
				t[rt] = id;
				chkmin(Mn[rt], min(calc(l, t[rt]), calc(r, t[rt])));
				return;
			}
			if (calc(l, id) >= calc(l, t[rt]) && calc(r, id) >= calc(r, t[rt])) return;
			if (calc(mid, id) <= calc(mid, t[rt])) swap(t[rt], id);
			insert(ls, l, mid, L, R, id);
			insert(rs, mid + 1, r, L, R, id);
			chkmin(Mn[rt], min(calc(l, t[rt]), calc(r, t[rt])));
			update(rt);
		}
		if (L <= mid) insert(ls, l, mid, L, R, id);
		if (R > mid) insert(rs, mid + 1, r, L, R, id);
		update(rt);
	}
	inline ll Query(int rt, int l, int r, int L, int R) {
		if (L <= l && r <= R) return Mn[rt];
		int mid = (l + r) >> 1; ll ret = INFLL;
		if (b[t[rt]] != INFLL) ret = min(calc(max(l, L), t[rt]), calc(min(r, R), t[rt]));
		if (L <= mid) chkmin(ret, Query(ls, l, mid, L, R));
		if (R > mid) chkmin(ret, Query(rs, mid + 1, r, L, R));
		return ret;
	}
		
} T;

int to[MAXN << 1], len[MAXN << 1], nxt[MAXN << 1], head[MAXN];
int dep[MAXN], sz[MAXN], fa[MAXN][25], son[MAXN], top[MAXN], dfn[MAXN];
int n, m, cnte, Id, tot;

inline void addedge(int x, int y, int z) { to[++cnte] = y; len[cnte] = z; nxt[cnte] = head[x]; head[x] = cnte; }
inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = 20; ~i; i--)
		if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
	if (x == y) return x;
	for (int i = 20; ~i; i--)
		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
inline void dfs1(int x, int fth) {
	dep[x] = dep[fth] + 1; sz[x] = 1; fa[x][0] = fth;
	for (int i = 1; i <= 20; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for (int i = head[x]; i; i = nxt[i]) {
		int y = to[i], z = len[i];
		if (y != fth) {
			dis[y] = dis[x] + (ll)z; dfs1(y, x); sz[x] += sz[y];
			if (sz[y] > sz[son[x]]) son[x] = y;
		}
	}
}
inline void dfs2(int x, int tp) {
	dfn[x] = ++Id; bl[Id] = x; top[x] = tp;
	if (son[x]) dfs2(son[x], tp);
	for (int i = head[x]; i; i = nxt[i]) {
		int y = to[i];
		if (y != fa[x][0] && y != son[x]) dfs2(y, y);
	}
}
inline void rangeAdd(int x, int y) {
//	cerr << "rangeAdd: " << x << ' ' << y << ' ' << top[x] << ' ' << top[y] << endl;
	while (top[x] != top[y]) {
//		cerr << "Range: " << dfn[top[x]] << ' ' << dfn[x] << endl;
		T.insert(1, 1, n, dfn[top[x]], dfn[x], tot); x = fa[top[x]][0];
	}
	T.insert(1, 1, n, dfn[y], dfn[x], tot);
}
inline ll Query(int x, int y) {
	ll ret = INFLL;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		chkmin(ret, T.Query(1, 1, n, dfn[top[x]], dfn[x]));
		x = fa[top[x]][0];
	}
	if (dep[x] > dep[y]) swap(x, y);
	chkmin(ret, T.Query(1, 1, n, dfn[x], dfn[y]));
	return ret;
}

int main() {
	n = read(); m = read();
	for (int i = 1; i < n; i++) {
		int x = read(), y = read(), z = read();
		addedge(x, y, z); addedge(y, x, z);		
	}
	dfs1(1, 0); dfs2(1, 1);
	k[++tot] = 0; b[tot] = INFLL;
//	for (int i = 1; i <= N; i++) cerr << dfn[i] << ' '; cerr << endl;
	T.Init(); T.build(1, 1, n);
	while (m--) {
		int opt = read(), s = read(), t = read();
		if (opt == 1) {
			int x = read(), y = read(), lca = LCA(s, t);
//			cerr << s << ' ' << t << ' ' << lca << endl;
			k[++tot] = -x; b[tot] = (ll)dis[s] * x + y;
			rangeAdd(s, lca);
			k[++tot] = x; b[tot] = (ll)(-2LL * dis[lca] + dis[s]) * x + y;
			rangeAdd(t, lca);
		} else printf("%lld\n", Query(s, t));
	}
	return 0;
}