《CF1824E LuoTianyi and Cartridge》 解题报告

发布时间 2023-10-06 19:45:52作者: daduoli

好题。

模拟赛出了这题,抽象。

初步化简:

由于 \(\min (A,C)\) 不好处理,我们考虑从大到小加边加点,或者从小到大删边删点。

一般题目是考虑加边加点好操作一点,这题是考虑删边删点好操作。

然后我们记当前枚举的 \(\min (A,C)\) 的最小值是多少,记为 \(x\) 。然后称大于等于 \(x\) 点权和边权的是合法的。

然后我们考虑合法的边中哪些是有用的,一条边有用当且仅当他两个端点的两边都存在合法点。

所以倘若某一条边的一端没有合法点,那么我们就可以把这条边给删掉了。

考虑删边和删点,删边的话,就把边的两个端点给缩起来就好了,然后点权合并;而对于删点可以直接暴力删掉(注意:允许空心点存在,即不存在合法点,但是要保证他不是叶子节点),倘若删完之后变成了变成了空心节点,还是叶节点,那么就删掉,其中可能导致连锁反应,父亲也是空点,然后现在变成了叶节点,那么从下往上删点即可。

这样我们就得到了一个新的树称作 \(G\) ,树边表示一条合法边,而树点表示由不合法边缩成的连通块

计算答案

我们现在考虑选出一个子树 \(T'\) ,点集为 \(V\) (注意 \(V\) 的大小指的是合法点的大小),边集为 \(E\) ,那么可以知道的是边的数量是 \(\min (V-1,E)\)

我们考虑怎样的选择是合法的,能保证选出来的是一棵树。

首先我们记 \(G\) 的实际的点数是 \(k\)\(V\) 指的是合法点个数。

  • 我们考虑当 \(\min (V-1,E)\) 受到 \(V-1\) 的限制是什么情况,就是说有很多点是空点,那么实际上所有点都会被选择,然后我们再任意选出前 \(V-1\) 大的边的权值加起来就好了。

那么问题来了这样为什么是对的呢。

因为首先你叶子节点一定不是空点,所以叶子节点一定是被选的,而只要你所有叶子节点都被选了,那么你无论加什么 边都一定可以使他连通(虽然我不会证明,但是的确看上去挺对的结论)

  • 考虑受到 \(E\) 的限制,这时候就说明你的合法点太多了,边不够支撑了,但是可以发现每个叶子节点的连通块中一定要选一个合法点,否则与他连着的这条边一定选不了。然后选完之后,你就可以发现,变成了和上面类似,剩下的点,以及所有边考虑怎么选,考虑剩下 \(p\) 条边,我们再选前 \(p\) 大的节点即可。

然后我们发现叶子节点中一定至少要选出一个点,这样一定是优的,否则与他连着的父边就选不了,而你又发现选完叶子节点之后,剩下的点边实际上无论怎么选都可以保证合法的这个性质,所以你就用线段树求前若干大就好了。

所以我们现在有 \(x=\min(A,C)\) 然后 \(T\) 的边数 \(cnt=\min(|V|-1,|E|)\) ,然后记叶子节点已经选了的有 \(lef\) 个,贡献是 \(num\)

那么答案有三部分,一个是 \(num\) ,一个是点权中前 \(cnt+1-lef\) 大的和,另一个是边权中前 \(cnt\) 大的和。

实现

我们要维护的东西:

  • \(G\) 中点所代表连通块中的点权

  • \(G\) 中点连通块连着的边

  • 维护每个叶子的最大值的和

  • 对于合法边权构成的权值线段树

  • 对于合法点去除叶节点已经选完后的权值线段树

  • 一个点是叶子当且仅当权值是 \(1\) ,所以节点 \(1\) 也可能是叶子

具体实现,合并两个点可以用 \(set\) 当然你用线段树合并也不是不行,用 \(set\) 启发式合并可以做到 \(\log^2 n\) ,然后对于前若干大,直接上线段树就好了。

总时间复杂度 \(O(n\log^2 n)\)\(Alex\_Wei\) 说可以用线段树合并 \(+\) 懒惰删除做到 \(O(n\log n)\) ,反正我没有码力写不来。