一类游走问题 ​

通常可以看作从根节点出发，每次扩展一小部分，但是不太规律，只能用贪心解决。

常见的情况下，我们应该设计一种方式，使得祖先一定先选，然后才是儿子选，且答案最优。

常见实现：可并堆，长链剖分。

例题 ​

[POI2006] MET - Subway ​

一看就是贪心。显然直径必选。考虑第二次怎么选。

有个naive的想法是分一下类，与直径相交和不相交。相交直接从直径上引出两条链，不相交很麻烦。

大胆猜想不会不相交，直接选就可以。发现是对的。为什么？

因为可以和上面的链交换一下端点，调整证明。

SDSZ：杀戮尖塔 ​

小Z最近接触了一款游戏，叫做《杀戮尖塔》。游戏中的主人公将会依次进入若干个房间。

可能为怪物房间（$a[i]<0$）——房间$i$内会有怪物减少主人公$(-a[i])$的血量；

可能为补给房间（$a[i]>0$）——房间$i$可以帮助主人公增加$(a[i])$的血量。

主人公可以多次经过同一个房间，但只有在第一次进入房间时才会触发该房间的房间效果。主人公的初始血量为$0$，当主人公的血量$<0$时，游戏失败。游戏的目标是要达到指定的$T$号房间。

$N$个房间之间由$N - 1$条双向通道相连，每条通道连接两个房间。一条通道只有当连接的两个房间至少一个房间的房间效果触发后才可以使用。

现在，小Z的主人公站在$1$号房间的入口处（还没有进入$1$号房间）。小Z希望得知他能否操作主人公到达号房间。

$lim:N\leq1e5$

solution ​

1. 将$T$及其子树的$a$合并成$inf$，将题目转化为求最大最终血量。
2. 如果没有血量总是非负的限制的话，可以直接DP。
3. 考虑怎么处理非负限制，$mi$表示遍历该块的过程中，$suma$的最小值，可以结合$suma$用来刻画限制。
4. 先考虑怎么直接贪。比较naive的想法是先选$mi$小的，然后不断提升自己的血量，就可以选更多$mi$小的。所以肯定是按$mi$从大到小排序。
5. 考虑父亲必须先选，所以将父亲在插入堆中时，把$mi$比他大的都合并了，并且得保证增幅非负。