AGC023F 01 on Tree
- 给出一棵 $n$ 个节点的树，以及一个空序列。
- 每个节点上有一个取值在 ${0, 1}$ 中的数。
- 每次你可以选择没有父亲节点的点删除，并且将这个节点上的数字放在当前数列末尾。
- 请你求出这个数列可能得到的最小逆序对数。
- $n\le 2\times 10^5 $
如果没有先删父亲的限制，那么最优序列一定形如 $0000\cdots 1111$。不妨先忽略这一限制，将所有点统一处理。选中某个点操作就将这个点和父亲“合并”，表示选完父亲后立即选这个点。这样是等价的。考虑从根出发，当前的最优决策一定会最先和根合并，而后继的操作最优性同理。多个点合并在一起后，新点不难表示为其 $0,1$ 的个数 $a_i,b_i$，两个点 $i,j$ 当满足 $b_ia_j<b_ja_i$ 时 $i$ 先选更优。使用优先队列维护合并，答案在合并过程中统计即可。
这一类贪心的本质是将序列的贪心放在树上，且限制生成序列的拓扑序，可以使用贪心选取前继化为类似于序列的问题，其中比较方法和序列相同。
HDU-6326 Monster Hunter
给出一棵 $n\le 10^5$ 个节点的树，你有一个初始血量，需要选择一个符合拓扑序的挑战顺序，每次挑战先将血量减小 $a_i$，再奖励 $b_i$ 血量。要求血量始终非负。求出最小初始值。
仍然先考虑问题放在序列上的求法，可以先选满足 $a_i\le b_i$ 且 $a_i$ 从小到大，再选 $a_i\gt b_i$ 且 $b_i$ 从大到小。树上合并时可以考虑先用父亲的 $b$ 抵消，再用 $a$。最后答案即为 $a_1$。
