题解：P7011 [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$ 可以不走，对应的 $f$ 为 $0$。然而用数对维护时不能很好的满足这个性质，所以需要将 $y<0$ 的数对和之后的位置进行合并，如果能够使得 $y>0$ 就插入，否则此时走该子树一定不优，全部清空即可（实际上只要判断在 $y>0$ 的时候放入就行了，因为如果加起来都小于 $0$ 那么堆一定是空的）。

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