目录
题目描述
一棵树，树上有 \(n\) 个节点，最初每个节点上有\(1\)个数字：\(123456789123456789\)。有两种操作：
\(\centerdot\)选择\(s,t\)两个节点，将路径上的每一个点都变多（\(1\)个变\(2\)个）数字：\(a\times dis+b\)，其中\(dis\)表示该节点到\(s\)的距离。
\(\centerdot\)选择\(s,t\)两个节点，找出路径上所有点的所有数字最小值。
解题思路
首先一眼树剖。需要将\(s,t\)之间的链剖出来。
然后可以很容易的得到一个式子：
其中\(i\)表示两点之间的某个节点。
然后分拆成\(s\)到\(lca\)和\(lca\)到\(t\)两部分：
*由于选择最小的节点数字，我们不得不将所有的点都化为一段一次函数放入树内。
*第二个式子可能不便于理解，可直接用总式子减去第一个式子。
发现可以李超树。注意直接维护min值就可以，所以要pushup。
李超树下传标记不方便，不如直接标记永久化。
这里总结一下关于李超线段树的模板(\(update\)部分)：
inline ll calc(int x , int id){//计算当前x坐标下的y值
return k[id] * x + b[id] ;
}
const double eps = 1e-9 ;
inline int cmp(double x , double y){//浮点数往往有精度误差
if(x - y > eps) return 1 ;//表示x更大
if(y - x > eps) return -1 ;//表示y更大
return 0 ;//相等
}
inline void update(int l , int r , int node , int li , int ri , int x){
//目标左区间，目标右区间，当前节点，当前左区间，当前右区间，当前一次函数编号
int mid = li + ri >> 1 ;//首先计算中点位置
if(l <= li && ri <= r){//是所求的区间内
if(calc(li , x) <= calc(li , t[node]) && calc(ri , x) <= calc(ri , t[node])){//如果当前函数段完全优于之前的函数段
t[node] = x ;//直接将之前的函数段替换掉
mn[node] = min(mn[node] , min(calc(li , x) , calc(ri , x))) ;
//由于单调性 此时权值线段树上维护的最小值只可能在左端或右端
return ;
}
if(calc(li , x) >= calc(li , t[node]) && calc(ri , x) >= calc(ri , t[node])) return ;//当前函数段完全劣于之前函数段 连看都不看
if(k[x] < k[t[node]]){//分讨 斜率大小
//可以证明斜率在负数时候依旧成立
if(calc(mid , x) <= calc(mid , t[node])) update(l , r , node<<1 , li , mid , t[node]) ,t[node] = x ;
//发现没有被完全包含 由于之前分讨的斜率关系，递归下传原来的标记（因为更优）并用此区间更优替换最优解（此时可以把最优解看作懒标记）
else update(l , r , node<<1|1 , mid + 1 , ri , x) ;
}else{
if(calc(mid , x) <= calc(mid , t[node])) update(l , r , node<<1|1 , mid + 1 , ri , t[node]) ,t[node] = x ;
else update(l , r , node<<1 , li , mid , x) ;
//只有在不被完全包含的情况下才打懒标记 否则直接下传
}
mn[node] = min(mn[node] , min(calc(li , x) , calc(ri , x))) ;//记得更新最小值（权值）
pushup(node) ;//由两个子树节点更新本节点
return ;
}
if(l <= mid) update(l , r , node<<1 , li , mid , x) ;
if(r > mid) update(l , r , node<<1|1 , mid + 1 , ri , x) ;
pushup(p) ;
}
可以画图理解关于最优点选取部分。
code
#include<iostream>
#include<cstdio>
using namespace std ;
#define ll long long
#define pdi pair<double,int>
const ll inf = 123456789123456789 ;
const int MAXN = 1e5+10 ;
const double eps = 1e-9 ;
inline ll read(){
ll x = 0 ,y = 1 ;
char c = getchar() ;
while(c < '0' || c > '9'){
if(c == '-') y = -1 ;
c = getchar() ;
}
while(c <= '9' && c >= '0'){
x = x * 10 + c - '0' ;
c = getchar() ;
}
return x * y ;
}
int n ,m ;
struct Edge{
int to ,next ;ll w ;
}edge[MAXN<<1] ;
int head[MAXN] ,edge_cnt ;
inline void edge_add(int from , int to , ll w){
edge[++edge_cnt].to = to ;
edge[edge_cnt].w = w ;
edge[edge_cnt].next = head[from] ;
head[from] = edge_cnt ;
}
ll dfn[MAXN] ,tp[MAXN] ,dep[MAXN] ,fa[MAXN] ,siz[MAXN] ,son[MAXN] ;
ll mn[MAXN<<2] ,t[MAXN<<2] ,b[MAXN<<2] ,dis[MAXN] ,bel[MAXN<<2] ;
ll k[MAXN<<2] ;
ll top[MAXN] ,cnt ;
inline ll calc(int x,int id) {return k[id]*dis[bel[x]]+b[id];}
inline void build(int p , int l , int r){
mn[p] = inf ;
t[p] = 1 ;
if(l == r) return ;
int mid = l + r >> 1 ;
build(p<<1 , l , mid) ;
build(p<<1|1 , mid + 1 , r) ;
}
inline void pushup(int x){
mn[x] = min(mn[x] , min(mn[x<<1] , mn[x<<1|1])) ;
}
inline void update(int nl , int nr , int p , int l , int r , int x){
int mid = l + r >> 1 ;
if(nl <= l && r <= nr){
if(calc(l , x) <= calc(l , t[p]) && calc(r , x) <= calc(r , t[p])){
t[p] = x ;
mn[p] = min(mn[p] , min(calc(l,x) , calc(r , x))) ;
return ;
}
if(calc(l , x) >= calc(l , t[p]) && calc(r , x) >= calc(r , t[p])) return ;
if(k[x] < k[t[p]]){
if(calc(mid , x) <= calc(mid , t[p])) update(nl , nr , p<<1 , l , mid , t[p]) ,t[p] = x ;
else update(nl , nr , p<<1|1 , mid + 1 , r , x) ;
}else{
if(calc(mid , x) <= calc(mid , t[p])) update(nl , nr , p<<1|1 , mid + 1 , r , t[p]) ,t[p] = x ;
else update(nl , nr , p<<1 , l , mid , x) ;
//只有在不被完全包含的情况下才打懒标记 否则直接下传
}
mn[p] = min(mn[p] , min(calc(l , x) , calc(r , x))) ;
pushup(p) ;
return ;
}
if(nl <= mid) update(nl , nr , p<<1 , l , mid , x) ;
if(nr > mid) update(nl , nr , p<<1|1 , mid + 1 , r , x) ;
pushup(p) ;
}
inline ll query(int ql , int qr , int p , int l , int r){
if(ql <= l && r <= qr) return mn[p] ;
int mid = l + r >> 1 ;
ll res = inf ;
if(b[t[p]] != inf) res = min(calc(max(l , ql) , t[p]) , calc(min(r , qr) , t[p])) ;
if(ql <= mid) res = min(res , query(ql , qr , p<<1 , l , mid)) ;
if(mid < qr) res = min(res , query(ql , qr , p<<1|1 , mid + 1 , r)) ;
return res ;
}
inline void dfs1(ll node , ll f){
fa[node] = f ;
siz[node] = 1 ;
dep[node] = dep[f] + 1 ;
for(ll i = head[node];i;i = edge[i].next){
ll v = edge[i].to ;
if(v == f) continue ;
dis[v] = dis[node] + edge[i].w ;
dfs1(v , node) ;
siz[node] += siz[v] ;
if(siz[son[node]] < siz[v]) son[node] = v ;
}
}
inline void dfs2(ll node , ll topp){
top[node] = topp ;
dfn[node] = ++cnt ;
bel[cnt] = node ;
if(son[node]) dfs2(son[node] , topp) ;
for(ll i = head[node];i;i = edge[i].next){
ll v = edge[i].to ;
if(v != son[node] && v != fa[node]) dfs2(v , v) ;
}
}
inline ll LCA(ll x , ll y){
while(top[x] != top[y]){
dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]] ;
}
return dep[x] > dep[y] ? y : x ;
}
ll tot ;
inline void updrange(ll u , ll v){//lca一定小于u
while(top[u] != top[v]){
update(dfn[top[u]] , dfn[u] , 1 , 1 , n , tot) ;
u = fa[top[u]] ;
}
update(dfn[v] , dfn[u] , 1 , 1 , n , tot) ;
}
inline ll ask(ll x , ll y){
ll ans = inf ;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]) swap(x , y) ;
ans = min(ans , query(dfn[top[x]] , dfn[x] , 1 , 1 , n)) ;
x = fa[top[x]] ;
}
if(dep[x] > dep[y]) swap(x , y) ;
return min(ans , query(dfn[x] , dfn[y] , 1 , 1 , n)) ;
}
int main(){
scanf("%d%d" , &n , &m) ;
for(int i = 1;i < n;++i){
int u ,v ;scanf("%d%d" , &u , &v) ;ll w = read() ;
edge_add(u , v , w) ;
edge_add(v , u , w) ;
}
dfs1(1 , 0) ;
dfs2(1 , 1) ;
k[++tot] = 0 ,b[tot] = inf ;
build(1 , 1 , n) ;
for(int i = 1;i <= m;++i){
int opt ;scanf("%d" , &opt) ;
ll s = read() ,t = read() ,lca = LCA(s , t) ,x ,y ;
if(opt == 1){
x = read() ,y = read() ;
k[++tot] = -x ;
b[tot] = x * dis[s] + y ;
updrange(s , lca) ;
k[++tot] = x ;
b[tot] = x * (dis[s] - 2 * dis[lca]) + y ;
updrange(t , lca) ;
}else{
printf("%lld\n" , ask(s , t)) ;
}
}
return 0 ;
}