题解
看错题了，以为单次修改相当于一个覆盖，后来才明白“添加”……
就相当于添加很多线段求最小值
首先这个等差数列添加的方式比较烦人，我们拆开两条链，一条s到lca，一条lca到t
那么s到lca上的点x值就是\(-A * dis[x] + A * dis[s] + B\)
lca到t上的点x值就是\(A * dis[x] + A * (dis[s] - 2 * dis[lca]) +B\)
这个时候就是点值代入的一次函数的形式，考虑怎么插入一条线段
这个线段树上的节点原来维护着一条直线，如果新加入的线段两端都小于原来线段，那么原来线段就替换掉
如果两端都大于，那么这条线段没用，退出
如果有交点，那么求出交点的位置，下取整，保留靠下的长度较长的一条线段，另一条线段根据交点的位置分到左右区间递归处理
听说叫什么李超线段树。。。
用可持久化处理区间最大值，每次询问的时候查询区间在当前节点的线段能取到的最小值
加上树链剖分，复杂度是\(O(n \log^3 n)\)
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define enter putchar('\n')
#define space putchar(' ')
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M;
struct Line {
int64 A,B;
Line(int64 _A = 0,int64 _B = 0){A = _A;B = _B;}
int64 cal(int64 x) {return A * x + B;}
};
struct node {
int to,next;
int64 val;
}E[MAXN * 2];
struct Tr_node {
int L,R;
Line f;int64 val;
bool cover;
}tr[MAXN * 4];
int sumE,head[MAXN];
int64 dis[MAXN];
int fa[MAXN],dep[MAXN],siz[MAXN],son[MAXN],top[MAXN],dfn[MAXN],idx,id[MAXN];
void build(int u,int l,int r) {
tr[u].L = l;tr[u].R = r;
tr[u].cover = 0;tr[u].val = 123456789123456789LL;
if(l == r) return;
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
}
int64 down(int64 A,int64 B) {
if(B < 0) A = -A,B = -B;
int64 C = A / B;
return C - (C * B > A);
}
int64 cross(Line f,Line g) {
return down(f.B - g.B,g.A - f.A);
}
void Add_Line(int u,Line g) {
int64 l = dis[id[tr[u].L]],r = dis[id[tr[u].R]];
tr[u].val = min(tr[u].val,min(g.cal(l),g.cal(r)));
if(!tr[u].cover) {tr[u].f = g;tr[u].cover = 1;return;}
else {
int64 mid = (tr[u].L + tr[u].R) >> 1;
mid = dis[id[mid]];
if(tr[u].f.cal(l) >= g.cal(l) && tr[u].f.cal(r) >= g.cal(r)) {
tr[u].f = g;return;
}
else if(tr[u].f.cal(l) <= g.cal(l) && tr[u].f.cal(r) <= g.cal(r)) return;
else if(tr[u].f.cal(l) <= g.cal(l)) {
if(cross(tr[u].f,g) <= mid) {Add_Line(u << 1,tr[u].f);tr[u].f = g;}
else Add_Line(u << 1 | 1,g);
}
else {
if(cross(tr[u].f,g) <= mid) {Add_Line(u << 1,g);}
else {Add_Line(u << 1 | 1,tr[u].f);tr[u].f = g;}
}
}
}
void Modify(int u,int l,int r,Line g) {
tr[u].val = min(tr[u].val,min(g.cal(dis[id[l]]),g.cal(dis[id[r]])));
if(tr[u].L == l && tr[u].R == r) {
Add_Line(u,g);
return ;
}
int mid = (tr[u].L + tr[u].R) >> 1;
if(r <= mid) Modify(u << 1,l,r,g);
else if(l > mid) Modify(u << 1 | 1,l,r,g);
else {Modify(u << 1,l,mid,g);Modify(u << 1 | 1,mid + 1,r,g);}
}
int64 Query(int u,int l,int r) {
int64 res = 123456789123456789LL;
if(tr[u].cover) {
res = min(res,tr[u].f.cal(dis[id[l]]));
res = min(res,tr[u].f.cal(dis[id[r]]));
}
if(tr[u].L == l && tr[u].R == r) {
res = min(res,tr[u].val);
return res;
}
int mid = (tr[u].L + tr[u].R) >> 1;
if(r <= mid) res = min(res,Query(u << 1,l,r));
else if(l > mid) res = min(res,Query(u << 1 | 1,l,r));
else {
res = min(res,Query(u << 1,l,mid));
res = min(res,Query(u << 1 | 1,mid + 1,r));
}
return res;
}
void Modify_Path(int s,int t,int64 A,int64 B) {
while(top[s] != top[t]) {
if(dep[top[s]] < dep[top[t]]) swap(s,t);
Modify(1,dfn[top[s]],dfn[s],Line(A,B));
s = fa[top[s]];
}
if(dep[s] > dep[t]) swap(s,t);
Modify(1,dfn[s],dfn[t],Line(A,B));
}
int64 Query_Path(int s,int t) {
int64 res = 123456789123456789LL;
while(top[s] != top[t]) {
if(dep[top[s]] < dep[top[t]]) swap(s,t);
res = min(res,Query(1,dfn[top[s]],dfn[s]));
s = fa[top[s]];
}
if(dep[s] > dep[t]) swap(s,t);
res = min(res,Query(1,dfn[s],dfn[t]));
return res;
}
void add(int u,int v,int64 c) {
E[++sumE].to = v;
E[sumE].next = head[u];
E[sumE].val = c;
head[u] = sumE;
}
void dfs1(int u) {
dep[u] = dep[fa[u]] + 1;
siz[u] = 1;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u]) {
fa[v] = u;
dis[v] = dis[u] + E[i].val;
dfs1(v);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
return;
}
void dfs2(int u) {
dfn[u] = ++idx;
id[idx] = u;
if(!top[u]) top[u] = u;
if(son[u]) {
top[son[u]] = top[u];
dfs2(son[u]);
}
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u] && v != son[u]) dfs2(v);
}
}
int find_lca(int a,int b) {
while(top[a] != top[b]) {
if(dep[top[a]] < dep[top[b]]) swap(a,b);
a = fa[top[a]];
}
return dep[a] < dep[b] ? a : b;
}
void Init() {
read(N);read(M);
int u,v;int64 w;
for(int i = 1 ; i < N ; ++i) {
read(u);read(v);read(w);
add(u,v,w);add(v,u,w);
}
dfs1(1);dfs2(1);
build(1,1,N);
}
void Solve() {
int op,s,t;
int64 A,B;
while(M--) {
read(op);read(s);read(t);
if(op == 1) {
read(A);read(B);
int f = find_lca(s,t);
Modify_Path(s,f,-A,A * dis[s] + B);
Modify_Path(f,t,A,A * (dis[s] - 2 * dis[f]) + B);
}
else {
out(Query_Path(s,t));enter;
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}
昨天真是奇颓无比
三体真好看