0%

「NOI2014」购票

「NOI2014」购票

给一棵以1为根的树,每个点$u$有属性$p_u,q_u,l_u$,边有边权。若$v$为$u$的祖先且$u,v$距离不超过$l_u$,则$u$可以花费$d(u,v)p_u+q_u$的代价跳到$v$上。问每个点跳到根的最短距离。

$n\le 2\times 10^5,p_u\le 10^6,q_u\le 10^{12},s_u\le l_u\le 2\times 10^{11},\sum s_u\le 10^{11}$

首先有一个暴力的dp。设$f(u)$表示$u$跳到根的最短距离。

直接做是$O(n^2)$.

这个式子看着很斜率优化,但有两个问题:对$v$的取值有限制,以及这是个树,一些在序列上均摊的做法在此复杂度可能不对。

做法1:

对$v$的取值有限制我们可以线段树维护凸壳。dfs的时候询问$[dep_u-l_u,dep_u]$这一段的凸壳求dp值,然后将其插入$dep_u$位置。但加入凸壳复杂度是均摊的,撤销之后再加入复杂度就挂掉了(如一条长链下面挂了很多儿子)。

补救方法也是有的,套个树剖上去,复杂度$O(n\log^ 3n)$听说也能过。

做法2:

考虑有根树点分。

设分治中心是$u$.先递归求父亲那一边的连通块的答案。然后提取出这个连通块中$u$的祖先。用这些祖先来更新$u$的答案。现在考虑$u$的祖先与$u$对剩余连通块的贡献。

首先必然可以用线段树维护这些点的凸壳,然后剩余点都在上面二分查,但复杂度也较高。

可以类似CDQ分治的思路,先把$u$的祖先与$u$以$dep$为关键字,剩余的点以$dep-l$为关键字一起排序,那么对于剩余的点$v$,应该在其右侧所有点上构成的凸包上查询,那么我们可以考虑右侧对左侧的贡献(建右侧的凸壳,左侧点在凸壳上二分),然后递归两边。直接做是2log,但可以通过归并少掉一个log,算上点分是$\mathcal O(n\log^ 2n)$.

My code