codeforces 2222F

· · 题解

警告：这个做法笔者并没有写代码验证正确性。

题意：考虑 k 个点 c_1,\cdots c_k。可以花费另一张图 G 中 c_x,c_y 两点的某条路径中的边权 \operatorname{mex} 连接 c_x,c_y。问连通 c_1,\cdots c_k 所花费的最小代价。

首先，显然无解当且仅当原图中 c_1\cdots c_k 不连通。我们注意到，想要连通 c_1\cdots c_k，最优方案一定是连最小生成树。求最小生成树，我们可以想到 \textrm {kruskal}。

做一些观察后，我们发现，(c_u,c_v) 边权 \le x 的一个充分条件是去除原图中边权为 x 的边，c_u,c_v 连通。并且，对所有的 x=0,\cdots m+1，反复利用充分条件，可以得到确切的边权最小值。

于是我们考虑线段树分治。对于每个 x，把边权为 x 的边在线段树 [0,x-1] 和 [x+1,m+1] 两个区间上设置。

然后我们对线段树进行 \rm dfs，然后利用可撤销并查集，并记录当前有哪些点对 (e_x,e_y) 被连接。进入结点时连接这个结点的边。只要搜索到叶子，就把当前的所有 (e_x,e_y) 作为边权为当前叶子对应的值的边执行 \textrm {kruskal}。然后清空 e 集合中的所有点对（正确性就是，如果一对点被连接过，那么考虑边权更大的时候再也不会用到了）。返回时撤销当前结点的边。当某一时刻所有的新图中要求的点都被连接时（可以通过记录 \textrm {kruskal} 的并查集的每个集合存在新图中被要求点的数量判断），就得到了最终结果。

时间复杂度 \mathcal O(m\log m\log n+n)，证明如下。空间复杂度 \mathcal O(m\log m+n)。

::::info[时间复杂度证明] 注意到每条原图的边被分到不超过 \log m 个区间里面，因此所有区间里面不超过 \mathcal O(m\log m) 条边，因此所有需要处理的 e 不超过 \mathcal O(m\log m) 个。每次处理在线段树的并查集需要 \mathcal O(\log n)（因为需要撤销而不能路径压缩，在 \textrm {kruskal} 的并查集中倒是不存在这个问题），因此总共时间复杂度就是 \mathcal O(m\log m\log n)。最后的 n 只是在 m<n 的时候为了保险加上的。 ::::