题解：P11834 [省选联考 2025] 岁月

Petit_Souris · 2025-06-30 10:49:14 · 题解

本题两大难点：

意识到题目中的条件就是缩点后 0 入度 SCC 恰好只有一个；
熟练掌握 DAG 容斥技巧，以及《主旋律》一题的解法；

观察到 C 性质部分分很多，大概率是完整解法的一个重要部分。首先考虑 C 性质如何解决。

现在所有边权都相等，那么就和最小生成树无关了，只需要有任何一棵外向生成树，图就合法。考虑所有可能成为生成树根的节点，很自然地观察到这些点应当组成一个 SCC，否则无法互相到达。进一步地，这个 SCC 应当是缩点后图中唯一的 0 入度 SCC。因此我们现在转化目标，枚举集合 S，计算 S 中点恰好组成唯一合法 SCC 的方案数 h_S。

发现计算一个点集强连通的方案数是不可避免的。不妨设这个方案数为 f_S。这个问题就是《主旋律》，下面回顾一下这个问题的解法。

回忆 DAG 计数的过程：我们用“不断删除所有 0 入度点”的过程来刻画一个 DAG，并使用容斥系数 (-1)^{k + 1} 来处理每次删除的不一定是所有 0 入度点的问题。放到这个问题上同理，我们考虑设 g_S 表示将 S 划分成若干个 0 入度 SCC 的带权求和，系数为 (-1)^{k + 1}。

考虑如何计算 g_S，我采用的方法或许和其他题解中略有区别。我们考虑对于 S，建立其所有导出子图和关于 g 的带权求和的双射。可以考虑如下等式：

2^{2e_{S}} = \sum\limits_{T \subseteq S, T\neq \emptyset}2^{2e_{S - T} + E(S - T, T)}g_T

其中 E(S, T) 表示两端分别在 S, T 中的无向边数量（两个方向只算一次），e_S 表示 S 内部的无向边数量。E(S, T) 可以用 e_{S \cup T} - e_{S} - e_{T} 计算。

这个等式成立的原因：两边都代表 S 的导出子图数量，右边相当于钦定 T 中均为 0 入度 SCC，剩下的边乱连。

那么移项之后，只需计算所有 g_T(T\subset S) 即可推出 g_S。初始化有 g_{\emptyset} = -1，这部分时间复杂度为 \mathcal O(3 ^ n)。

接下来计算 f_S。我们可以考虑用 g, f 之间的递推式解决：

g_{S} = \sum\limits_{T \subseteq S, \mathrm{lowbit}(S) \in T}-f_{T}g_{S - T}

（g 的意义就是划分成若干个 SCC，互相不连边）

同理移项后可以表示出 f_{S}，时间复杂度也是 \mathcal O(3 ^ n)。

最后考虑如何计算答案。“恰好”的条件不好处理。考虑先做一步容斥：枚举 T\supseteq S，钦定 T 中的点组成了若干个合法 SCC。设 T - S 中的点组成了 k 个 SCC，那么相当于违反了 k 个限制，容斥系数为 (-1) ^ k。观察到这个系数就是 -g_{T - S}。

对于剩下的边，我们还有：

因此 T 对 h_S 的贡献即为 -f_{S}g_{T - S}2^{2e_{U - T} + E(U - T, T)}。

至此 C 性质被解决。时间复杂度 \mathcal O(3 ^ n)，代码。

接下来考虑正解，这里才正式开始和最小生成树的条件对决。

考虑 Kruskal 的过程，我们从小到大合并连通块。显然无论生成树取了什么，在合并完所有 \le w 的边之后得到的连通性应当是相同的。同理，放到有向图上，弱连通性也得是相同的。

那么我们可以这样判断一张图是否合法：

从小到大扫描 w，维护目前每个联通块可能成为根的点集（下面称为根集）。加入所有权值为 w 的边时，尽可能合并所有的连通块，并更新根集。最后根集非空即为合法。

下面称连通块为大点，我们考虑大点之间的图。

考虑根集应当如何合并：我们称一条边是关键边，当且仅当其终点属于根集。那么显然只需要保留所有关键边，这些关键边应当存在大点之间的一棵外向生成树。那么新的根集就是可能成为大点外向树的根对应的大点的根集之并。

可能说起来比较绕。实际上就是找到所有可能成为大图中的树根的点，这些点对应的原连通块，找到这些连通块中可能是根的点，并起来就是新的根。

发现这实际上形如若干个 C 性质的问题并起来。因此类似考虑容斥，大体过程类似，区别在于：

算答案的时候，要考虑 S 和 T - S 间的非关键边，以及 U - T 向 T 连的非关键边。

注意还有可能有无效的边（无论如何都不会在生成树里），给答案全局 \times 4 即可。

时间复杂度还是 \mathcal O(3 ^ n)（参考其他题解证明），注意实现细节。代码。