[BZOJ2157/Luogu1505][国家集训队]旅游(树链剖分,线段树)

发布于 2018-01-24  9 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2157/Luogu1505][国家集训队]旅游(树链剖分,线段树)

Description

Ray 乐忠于旅游,这次他来到了T 城。T 城是一个水上城市,一共有 N 个景点,有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本,T 城的任意两个景点之间有且只有一条路径。换句话说, T 城中只有N − 1 座桥。
Ray 发现,有些桥上可以看到美丽的景色,让人心情愉悦,但有些桥狭窄泥泞,令人烦躁。于是,他给每座桥定义一个愉悦度w,也就是说,Ray 经过这座桥会增加w 的愉悦度,这或许是正的也可能是负的。有时,Ray 看待同一座桥的心情也会发生改变。
现在,Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时,他还想知道某段路上最美丽的桥所提供的最大愉悦度,或是某段路上最糟糕的一座桥提供的最低愉悦度。

Http

BZOJ
Luogu

Tag

树链剖分,线段树

解决思路

把边权下放到它下面的点上维护,树链剖分后,线段树维护区间和、区间最大值、区间最小值,\(Lazy\)维护区间是否全部取负数。
思路不难,但代码量较大

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2157/Luogu1505][国家集训队]旅游(树链剖分,线段树)


HNCJ OIer 一枚