bzoj 4515 [Sdoi2016]游戏
内容
Description
Alice 和 Bob 在玩一个游戏。
游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 123456789123456789。
有时，Alice 会选择一条从 s 到 t 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r，
若 r 与 s 的距离是 dis，那么 Alice 在点 r 上添加的数字是 a×dis+b。有时，Bob 会选择一条从 s 到 t 的路径。
他需要先从这条路径上选择一个点，再从那个点上选择一个数字。
Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。
Input
第一行两个数字 n、m，表示树的点数和进行的操作数。
接下来 n−1 行，每行三个数字 u、v、w，表示树上有一条连接 u、v 的边，长度是 w。
接下来 m 行。每行第一个数字是 1 或 2。
若第一个数是 1，表示 Alice 进行操作，接下来四个数字 s、t、a、b。
若第一个数是 2，表示 Bob 进行操作，接下来四个数字 s、t。
Output
每当 Bob 进行操作，输出一行一个数，表示他能够选择的最小的数字
Sample Input
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
题解
这是个李超线段树。以前写个全部修改单点查询的。。这个是区间修改区间查询的。。
所以要定位到合适的区间再用那个题的方法下放直线。并且因为不能每次查询到最底层所以要对每个节点维护一个Min。并且还有一个问题就是那个题是序列，序列的下标一定是递增的；但这个题是树，往上跑和往下跑都可以，所以自变量不一定是递增还是递减，为了方便比较所以要把所有直线化成同一种形式，要么自变量递增，要么自变量递减。
在查询操作的时候和普通线段树没有多大区别，就是在对路径上所有直线取Min然后在定位到一个完全包含的区间的时候要用维护的那个Min再比较一下。在修改的时候要对直线方程做一下变形让它适应当前定位到的那个区间，就是保证带进去的直线一定是随着下标递增自变量也递增的。
#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),
add(x, y, z),add(y, x, 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);
else printf("%lld\n", ask(x, y));
}
}