526互联

luogu P4069 [SDOI2016] 游戏 题解【李超树+树剖】

发布时间 2023-07-29 17:47:57作者: adolf_stalin

目录

题目描述

P4069 [SDOI2016] 游戏

一棵树，树上有 \(n\) 个节点，最初每个节点上有\(1\)个数字：\(123456789123456789\)。有两种操作：
\(\centerdot\)选择\(s,t\)两个节点，将路径上的每一个点都变多（\(1\)个变\(2\)个）数字：\(a\times dis+b\)，其中\(dis\)表示该节点到\(s\)的距离。
\(\centerdot\)选择\(s,t\)两个节点，找出路径上所有点的所有数字最小值。

解题思路

首先一眼树剖。需要将\(s,t\)之间的链剖出来。
然后可以很容易的得到一个式子：

\[ans=\min \{a\times (dis[i]-dis[s])+b\} \]

其中\(i\)表示两点之间的某个节点。
然后分拆成\(s\)到\(lca\)和\(lca\)到\(t\)两部分：

\[y=-a\times dis[i] + (a\times dis[s]+b) \]

\[y=a\times dis[i]+a\times (dis[t]-dis[lca]\times 2) \]

*由于选择最小的节点数字，我们不得不将所有的点都化为一段一次函数放入树内。
*第二个式子可能不便于理解，可直接用总式子减去第一个式子。

发现可以李超树。注意直接维护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 ;
}