题意
Alice 和 Bob 在玩一个游戏。
游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 123456789123456789。
有时，Alice 会选择一条从 s 到 t 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r，
若 r 与 s 的距离是 dis，那么 Alice 在点 r 上添加的数字是 a×dis+b。有时，Bob 会选择一条从 s 到 t 的路径。
他需要先从这条路径上选择一个点，再从那个点上选择一个数字。
Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。
题解
很容易看出是树剖+李超线段树，但是小细节很多，比较容易挂。
李超线段树的横轴为dfn编号对应节点的树上前缀和，然后插入线段加上一定的偏移。插入的时候注意不同方向的影响。
李超线段树要求区间最小值，要加个pushup（其实这个板子我是抄的）
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FILE freopen("3.in","r",stdin),freopen("res.txt","w",stdout)
#define FI freopen("3.txt","r",stdin)
#define FO freopen("res.txt","w",stdout)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 123456789123456789
const int N = 1e6 + 10;
const double eps = 1e-5;
/***************树剖******************/
int son[N], siz[N], h[N], nxt[N], dep[N], p[N], fa[N], top[N], cnt, rnk[N], dfn[N], wi[N], si;
ll sum[N];
int n, m;
void dfs1(int o) {
son[o] = -1;
siz[o] = 1;
for (int j = h[o]; j; j = nxt[j])
if (!dep[p[j]]) {
dep[p[j]] = dep[o] + 1;
sum[p[j]] = sum[o] + wi[j];
fa[p[j]] = o;
dfs1(p[j]);
siz[o] += siz[p[j]];
if (son[o] == -1 || siz[p[j]] > siz[son[o]]) son[o] = p[j];
}
}
void dfs2(int o, int t) {
top[o] = t;
cnt++;
dfn[o] = cnt;
rnk[cnt] = o;
if (son[o] == -1) return;
dfs2(son[o], t); // 优先对重儿子进行 DFS，可以保证同一条重链上的点 DFS 序连续
for (int j = h[o]; j; j = nxt[j])
if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}
void add(int u, int v, int w) {
si++;
nxt[si] = h[u];
h[u] = si;
p[si] = v;
wi[si] = w;
}
/******************树剖*******************/
/****************超哥线段树****************/
ll k[N], b[N];
struct LiChaoTree {
#define ls rt << 1
#define rs rt << 1 | 1
int t[N << 2]; ll Mn[N << 2];
inline void Init() { t[0] = 1; Mn[0] = INF; }
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)sum[rnk[x]] + b[id]; }
inline void build(int rt, int l, int r) {
t[rt] = 1; Mn[rt] = INF;
if (l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
update(rt);
}
void chkmin(ll &t, ll x) {
t = min(t, x);
}
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 = INF;
if (b[t[rt]] != INF) 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;
/****************超哥线段树****************/
/******************询问*******************/
ll length(int u, int v) {
ll res = 0;
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
int f = fa[top[u]];
res += sum[u] - sum[f];
u = f;
} else {
int f = fa[top[v]];
res += sum[v] - sum[f];
v = f;
}
}
res += abs(sum[u] - sum[v]);
return res;
}
int ssi = 1;
void modify(int u, int v, ll a, ll c) {
int st = u;
int ed = v;
ll len = length(u, v);
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
int l = dfn[top[u]], r = dfn[u];
// 两种情况方向不一样
k[++ssi]= -a;
b[ssi] = c + a * sum[st];
T.insert(1, 1, n, l, r, ssi);
u = fa[top[u]];
} else {
int l = dfn[top[v]], r = dfn[v];
// 两种情况方向不一样
k[++ssi]= a;
b[ssi] = c + a * (len - sum[ed]);
T.insert(1, 1, n, l, r, ssi);
v = fa[top[v]];
}
}
if(dep[u] > dep[v]) {
int l = dfn[v], r = dfn[u];
k[++ssi]= -a;
b[ssi] = c + a * sum[st];
T.insert(1, 1, n, l, r, ssi);
} else {
int l = dfn[u], r = dfn[v];
k[++ssi]= a;
b[ssi] = c + a * (len - sum[ed]);
T.insert(1, 1, n, l, r, ssi);
}
}
ll qmin(int u, int v) {
ll res = INF;
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
int l = dfn[top[u]], r = dfn[u];
res = min(res, T.Query(1, 1, n, l, r));//(1, n, l, r, 1));
u = fa[top[u]];
} else {
int l = dfn[top[v]], r = dfn[v];
res = min(res, T.Query(1, 1, n, l, r));
v = fa[top[v]];
}
}
int l = dfn[v], r = dfn[u];
if(l > r) swap(l ,r);
res = min(res, T.Query(1, 1, n, l, r));
return res;
}
/******************询问*******************/
int main() {
//FILE;
dep[1] = 1;
cin >> n >> m;
T.Init();
T.build(1, 1, n);
k[1] = 0, b[1] = INF;
for(int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs1(1);
dfs2(1, 1);
while(m--) {
int ty;
cin >> ty;
if(ty == 1) {
ll s, t, a, b;
cin >> s >> t >> a >> b;
modify(s, t, a, b);
} else {
int s, t;
cin >> s >> t;
cout << qmin(s, t) << endl;
}
}
}