# bzoj 4515 [Sdoi2016]游戏

### Description

Alice 和 Bob 在玩一个游戏。

Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

### Output

3 5

1 2 10

2 3 20

2 1 3

1 2 3 5 6

2 2 3

1 2 3 -5 -6

2 2 3

#### Sample Output

123456789123456789

6

-106

### HINT

n≤100000，m≤100000，∣a∣≤10000,0<=w，|b|<=10^9

### 题解

#include <cstdio>
#include <cstring>
#include <algorithm>
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define inf 123456789123456789ll
using namespace std;
const int N = 100010;
struct edge {
int to, next;
long long v;
}e[N << 1];
int st[N], siz[N], top[N], son[N], fa[N], deep[N], w[N], pos[N];
int tot, n, m, x, y, root, dfs_id;
long long mins[N << 2], dis[N];
struct segt {
long long k, b; int pos;
segt() {}
segt(long long kk, long long bb, int x) : k(kk), b(bb), pos(x) {}
long long calc(int x) {
return k * (long long)(dis[x] - dis[pos]) + b;
}
}t[N << 2];
void add(int x, int y, long long z) {
e[++tot].next = st[x], e[tot].v = z;
e[tot].to = y, st[x] = tot;
}
void dfs1(int now, long long las) {
siz[now] = 1, dis[now] = dis[fa[now]] + las;
for (int i = st[now]; i; i = e[i].next)
if (e[i].to != fa[now]) {
fa[e[i].to] = now, deep[e[i].to] = deep[now] + 1;
dfs1(e[i].to, e[i].v), siz[now] += siz[e[i].to];
if (siz[son[now]] < siz[e[i].to])
son[now] = e[i].to;
}
}
void dfs2(int now, int tp) {
top[now] = tp, w[now] = ++dfs_id, pos[dfs_id] = now;
if (son[now]) dfs2(son[now], tp);
for (int i = st[now]; i; i = e[i].next)
if (e[i].to != fa[now] && e[i].to != son[now])
dfs2(e[i].to, e[i].to);
}
int lca(int x, int y) {
while (top[x] != top[y]) deep[top[x]] > deep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
return deep[x] > deep[y] ? y : x;
}
void build(int rt, int l, int r) {
t[rt] = segt(0, inf, 0), mins[rt] = inf;
if (l == r) return;
build(lson), build(rson);
}
void inserts(int rt, int l, int r, segt x) {
long long te = min(x.calc(pos[l]), x.calc(pos[r]));
if (l == r) {
if (te < t[rt].calc(pos[l])) t[rt] = x, mins[rt] = te;
return;
}
segt tmp = t[rt];
te = min(te, mins[rt]);
if (x.k > tmp.k) swap(x, tmp);
if (x.calc(pos[mid]) < tmp.calc(pos[mid]))
t[rt] = x, mins[rt] = min(mins[rt], te),
inserts(lson, tmp);
else
t[rt] = tmp, mins[rt] = min(mins[rt], te),
inserts(rson, x);
}
void modify(int rt, int l, int r, int L, int R, segt x) {
if (L <= l && R >= r) {
inserts(rt, l, r, x); return;
}
if (L <= mid) modify(lson, L, R, x);
if (R >  mid) modify(rson, L, R, x);
mins[rt] = min(mins[rt], min(mins[rt << 1], mins[rt << 1 | 1]));
}
long long query(int rt, int l, int r, int L, int R) {
int le = max(l, L), ri = min(r, R);
long long ans = min(t[rt].calc(pos[le]), t[rt].calc(pos[ri]));
if (L <= l && R >= r) return min(ans, mins[rt]);
if (L <= mid) ans = min(ans, query(lson, L, R));
if (R >  mid) ans = min(ans, query(rson, L, R));
return ans;
}
void update(int x, int y, long long k, long long b) {
segt tem = segt(0, 0, 0);
int l = lca(x, y), s = x;
bool rec = 1; long long base;
while(top[x] != top[y]) {
if (deep[top[x]] < deep[top[y]]) swap(x, y), rec ^= 1;
base = dis[top[x]] + dis[s] - 2 * dis[l];
if (rec) base = dis[s] - dis[top[x]];
base = k * base + b;
if (!rec) tem = segt(k, base, top[x]);
else tem = segt(-k, base, top[x]);
modify(1, 1, n, w[top[x]], w[x], tem);
x = fa[top[x]];
}
if (deep[x] > deep[y]) swap(x, y);
else rec ^= 1;
base = dis[x] + dis[s] - 2 * dis[l];
if (rec) base = dis[s] - dis[x];
base = k * base + b;
if (!rec) tem = segt(k, base, x);
else tem = segt(-k, base, x);
modify(1, 1, n, w[x], w[y], tem);
}
long long ask(int x, int y) {
long long ans = inf;
while (top[x] != top[y]) {
if (deep[top[x]] < deep[top[y]]) swap(x, y);
ans = min(ans, query(1, 1, n, w[top[x]], w[x]));
x = fa[top[x]];
}
if (deep[x] > deep[y]) swap(x, y);
ans = min(ans, query(1, 1, n, w[x], w[y]));
return ans;
}
main() {
int x, y, z, t, a, b;
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++i)
scanf("%d%d%d", &x, &y, &z),
dfs1(1, 0), dfs2(1, 1), build(1, 1, n);
for (int i = 1; i <= m; ++i){
scanf("%d%d%d", &t, &x, &y);
if (t == 1) scanf("%d%d", &a, &b), update(x, y, a, b);