先把 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 不降顺序求答案,所以可以用堆维护信息。合并两个子树的时候用启发式合并或者可并堆,重点考虑新增一个点。