Doqe @ 2022-11-23 15:35:38
比如 P4437。
给你一些点，有先后顺序，必须选择一个点的父亲后才能选这个点，每个点有权值
怎么证明弹出某个点后将其与父亲合并的方法是对的。
以及如果选择这些点也会有不同时间花费怎么做（就比如选则这个点后时间戳加上
by FxorG @ 2022-11-23 16:14:52
@Doqe 这个感觉就是父亲后面接的一定是它，即你每个点实际上是一个序列，这个感觉用排序不等式一些理论就好了吧。因为你每次选“权值”最小的，而这个 cmp 定义两个元素的先后顺序是根据哪个先 使得新增权值更小来的。
by Doqe @ 2022-11-23 16:20:29
@FxorG 但是没有严格证明，甚至还有更加复杂的情况，比如一个父节点没有和自己的儿子完全合并就和上面的合了
by FxorG @ 2022-11-23 16:28:21
@Doqe 那你剩下的儿子直接跟父亲的上面合啊，这个部分维护个并查集，表示每个点，当其儿子要合并到它的时候，要合并到哪个点。
by Doqe @ 2022-11-23 17:20:26
@FxorG 我要的是证明，请看标题，做法都知道
by GIFBMP @ 2022-11-23 19:46:29
我记得魔塔中全蓝宝石转换塔的评论区的链接里好像有这一类问题的证明（我第一次了解这类贪心就是从魔塔中学的）