QOJ 6662

[[2023年10月18日总结#下午|引用自2023年10月18日总结]]

然后学习 qoj6662 。是韩语，翻译出来的题又要理解好久（可恶)。这里推荐 bing 翻译，稍微好理解一点点，但也没好到哪里去。至于题解，我将那个 pdf 翻译了，就像是在考古一样去猜测意思，挺有趣的。

首先我花了几个小时去翻译并理解题意，我太难了。后来发现这个好像 ppt 里写错题号了，mislead 我半天（)。但是不妨碍我去做这道题。这道题大概就是这个样子的。给一个树，然后求对于任意一个节点编号区间，让这个区间内所有点联通的最小边权和之和。这道题也非常有启发意义。首先我们将问题进行转化，本来相当于是以区间为主元，然后现在将主体换到一条边上。我们就看有哪些区间会经过这条边。于 z是我们就想到了染色，就是将这条边两边的分别染色，看有哪些区间会包含两种颜色。然后我们就得到了的算法。我们再通过链，发现可以用 set 来维护编号序列上黑色点的区间，然后单点修改。然后再拓展到树上，发现每次染色就是染一个子树，于是乎，我们就能自然而然地想到 [[启发式合并]]，处理完子树，然后将小的合并到大的，就能解决这道题！amazing！提交记录：qoj