首页 > 题解 > bzoj 4515 [Sdoi2016]游戏

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再比较一下。在修改的时候要对直线方程做一下变形让它适应当前定位到的那个区间,就是保证带进去的直线一定是随着下标递增自变量也递增的。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×