题解:P7011 [CERC2013] Escape

· · 题解

[CERC2013] Escape

先把 t 和一个虚点连边,将虚点的权值设为 +\infty,那么只需要判断能得到的最大精力是否为 +\infty 即可。

注意到一个点是否经过与其子树中的精力有关,所以只能考虑 dp

f_{u,i} 表示到达 u 点前精力为 i,在 u 子树中最多能增加多少的精力。转移时暴力合并即可,复杂度极高。

考虑优化。观察到 f_u 肯定由一些值相同的连续段构成,而所有的 f_u 的连续段数量之和大概是 \operatorname{O}(n) 的,所以考虑用若干个 pair 来表示 f。记 \{x,y\} 表示当初始精力大于等于 x 时最终的精力可以相较于初始精力小于 x 增加 y。那么最终统计答案时按照 x 从小到大考虑,如果当前精力大于等于 x 就把当前精力加上 y 即可。

由于要保证 x 不降顺序求答案,所以可以用堆维护信息。合并两个子树的时候用启发式合并或者可并堆,重点考虑新增一个点。

假设增加的点为 u,权值为 a_u,分类讨论权值正负。a_u\geq 0 时直接将 \{0,a_u\} 加入堆中。a_u<0 时相当于当前子树需要大于等于 -a_u 的精力才能进入,所以对于 x<-a_u 的那些数对要将 x 加上 -a_u

这样还不够,因为我们的 dp 数组实际上还有一个性质,当前子树内的权值小于 0 可以不走,对应的 f0。然而用数对维护时不能很好的满足这个性质,所以需要将 y<0 的数对和之后的位置进行合并,如果能够使得 y>0 就插入,否则此时走该子树一定不优,全部清空即可(实际上只要判断在 y>0 的时候放入就行了,因为如果加起来都小于 0 那么堆一定是空的)。

直接用堆维护就可以做到 \operatorname{O}(n\log^2n) 了,用可并堆可以做到 \operatorname{O}(n\log n),但没必要。