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

本题两大难点：

观察到 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$ 的带权求和的双射。可以考虑如下等式：

其中 $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$ 的意义就是划分成若干个 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 性质的问题并起来。因此类似考虑容斥，大体过程类似，区别在于：

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

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