我们尝试类比序列上的情况来看这一题。 对于序列上的情况,我们维护一个集合 ,其中 表示,长度为 的 …
CF1009F Dominant Indices
首先介绍一下我们亲爱的dsu on tree,也就是(一种?)树上启发式合并。 它本质上就是一种优化的暴力:对 …
lp3302 SDOI2013 森林
我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出 …
lp5290 十二省联考2019 春节十二响
首先我们考虑一种n^2logn的做法:将所有的子程序根据内存消耗来排序,然后每一次选中内存消耗最大且尚未被选中 …
CF600E Lomsat gelral
一道树上启发式合并的例题。 首先考虑暴力的做法。统计每一个子节点的信息,然后传到父节点。 我们发现这样做的复杂 …