首页 > 其他分享 >luogu P4069 [SDOI2016] 游戏 题解【李超树+树剖】

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

时间:2023-07-29 17:57:17浏览次数:43  
标签:return 树剖 int 题解 top luogu calc ll dis

目录

题目描述

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 ;
} 

标签:return,树剖,int,题解,top,luogu,calc,ll,dis
From: https://www.cnblogs.com/adolf-stalin/p/17590076.html

相关文章

  • P3979 遥远的国度 题解
    P3979遥远的国度题意一棵树,\(n\le10^5\),三个操作,\(m\le10^5\),点带权。换根路径推平子树查最小值思路如果没有换根,操作2,3是裸的树剖,考虑换根后的询问如何处理。显然不能再做一遍树剖,只能假装我们换根了,询问可以分成四种情况,令原根为\(root\),新根为\(id\),查询点......
  • luogu P3733 [HAOI2017] 八纵八横 题解【线段树分治+线性基+可撤销并查集+bitset】
    目录题目大意解题思路code题目大意题目链接给出一张\(n\)个点\(m\)条边的连通无向图,边带边权\(w_i\)。有以下三种操作,共\(q\)次:\(\centerdot\)在点\(x,y\)之间加入一条边权为\(w_i\)的边,如果这是第\(i\)个此种操作,则记这条新边为第\(i\)条。\(\centerdot\)将第\(k......
  • P9459 浴眼盯真 题解
    由于我不会使用正则表达式,所以我只能使用基础Python语法QwQ。[input().split()for_inrange(int(input()))]是个列表生成器,效果是产生一个长度为\(T\)的列表,列表的元素是以每一行以空格为分割符的字符串列表。for(a,b,c,d)in[]可以用\(a,b,c,d\)来复制列表中每个元素......
  • P9451 [ZSHOI-R1] 新概念报数 题解
    满足\(\operatorname{popcount}(x)<3\)的数实际上很少,直接把所有这些数扔到set里面,询问就返回set中\(x\)的下一个元素即可。记得开longlong。set内的元素数量是\(\log^2w\),所以复杂度是\(\mathcalO(\log^2w\log\log^2w+T\log\log^2w)=\mathcalO(\log^2w\log\logw......
  • 【题解】Luogu[P4711] 「化学」相对分子质量
    Link一道简单的模拟题,评绿可能有点高了。因为没有括号嵌套,难度瞬间降了一个档次,我们直接对着化学式扫一遍即可。若扫到左括号,说明接下来都是在括号内的,我们标记一下。若扫到大写字母,说明出现了一个新的元素,那么我们就看后面是否有下标,若有则类似于快读的方式直接处理后面的数......
  • [USACO13DEC] The Bessie Shuffle S 洗牌 题解
    提供一种思路,可以做到\(O(n)\)。目前是全OJ最优解,跑到了79ms。update2023.07.29完工,期望无bug(暑假快乐吖o( ̄▽ ̄)ブ)update2023.07.27(要原题检测了,先占个坑,有时间再补)原题大意P3095[USACO13DEC]TheBessieShuffleS有\(n\)张牌,每次取出\(m\;(m<n)\)张牌进行置换操作。操......
  • CF858C 题解
    洛谷链接&CF链接本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。题目简述给你一个均为小写字母的字符串,如果它的子串同时满足:三个连着的辅音字母。这一段连着的辅音字母不是全部一样的。就认为它不合法。现在要求用最少的空格隔开这个字符串,使得它变成......
  • AT_agc022_a 题解
    洛谷链接&Atcoder链接本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。题目简述给定字符串\(S\),仅包含互不相同的小写字母,你需要找到仅包含互不相同的小写字母的字符串中,第一个字典序比它大的字符串,如果找不到输出\(-1\)。(\(|S|\le26\))思路这篇题解......
  • 【题解】[2023牛客多校] Qu'est-ce Que C'est?
    题目传送门:[2023牛客多校]Qu'est-ceQueC'est?题意给定\(n,m\)构造\(a_{1},a_{2},...,a_{n}\),其中\(a_{i}\in[-m,m]\)之间取值。需要保证序列任意连续子段和都非负。\(0\leqn,m\leq5000\)分析记录合法序列的最小后缀。通过最小后缀来判断下一个数的取值范围。......
  • Codeforces Round 888 (Div. 3) 题解
    考场上\(7\)题做出来\(4\)题,最后几分钟才把D题调出来,但还是吃了不少罚时A.EscalatorConversations\(O(n)\)枚举即可,对于每个人计算需要的间隔台阶数是否在\((0,m)\)以内以及相差高度是否是\(k\)的倍数B.ParitySort显然,偶数和奇数是不可能产生交换操作的,而偶数......