自动搬运

查看原文

来自洛谷，原作者为

	chenxinyang2006 退役了，生涯回忆有空的时候再写

搬运于2025-08-24 23:10:37，当前版本为作者最后更新于2025-03-02 19:41:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

记号：$U=\{1,2...n\}$ 点的全集。

对于 C 性质， $G'$ 合法充要于存在一个点 $u$ 使得 $u$ 在 $G'$ 上可达所有点。

先来考虑更为简化的一个情况：必须 $u=1$ 在 $G'$ 上可达剩余所有点才认为合法，该情况该如何解决？

可以做类似 连通无向图计数 的操作：设 $f_S$ 表示 $S$ 导出子图内的边按照所述方式随机是否保留，那么 $1$ 可达 $S$ 内所有点的概率，这里我们认为只有 $1 \in S$ 时 $f_S$ 才有意义。那么考虑不合法的情况必定是 $1$ 只可达 $S$ 的某个真子集 $T$，容斥减去这些情况即可。记 $cross(S,T)$ 为 $S,T$ 两个集合间的连边数（默认 $S \cap T=\varnothing$），转移应是 $f_S=1-\sum\limits_{T \subsetneq S,1 \in T} f_T 2^{-cross(S-T,T)}$。

但事实上限制是 “存在一个点 $u$”，假设这样合法的点 $u$ 构成集合 $P$。那么在 $G'$ 上，$P$ 导出子图就应强连通，并且所有不在 $P$ 内的点必然不能有边指向 $P$ 内的点。除此之外要求 $P$ 内所有点可达所有 $1 \sim n$，这部分的概率可以用上述 DP 计算，只需改为认为只有 $P \subseteq S$ 时 $f_S$ 才有意义即可。这三部分的概率都是独立的可以分别计算出后相乘，对所有 $P \subseteq \{1,2...n\}$ 求出 $P$ 导出子图强连通的概率与 主旋律 的做法一致。这样我们确实得到了一个 C 性质能跑的做法，但做 $f$ 的 DP 的部分太慢了。$4^n$ C 性质

观察这份代码，$f$ 的转移可以视作在有向图上游走：对于 $T \subsetneq S$，$T \to S$ 有一条权重为 $-2^{-cross(S-T,T)}$ 的边，记一条路径的权值为其上所有边的边权之积。对于 $P$ 而言，希望求出的值其实是所有起点 $P'$ 满足 $P \subseteq P'$，且终点为 $U$ 的 $P' \to U$ 的所有路径的权值和。倒过来设 $f'_T$ 为 $T \to U$ 所有路径权值和，可以 $O(3^n)$ 求出所有 $f'_T$，再做一次超集和即可求出需要的值。$3^n$ C 性质

接下来考虑原问题，对于一颗选定的 $G'$ 的外向生成树，它和 $G$ 的最小生成树边权和相同实际上当且仅当对任意的 $v \in \Z$，连上所有边权 $\le v$ 的所有边得到的图的连通性，与连接外向生成树边权 $\le v$ 的所有边并视有向图为无向图后得到的图的连通性是完全一致的。这里 $G_1,G_2$ 的连通性完全一致定义为 $\forall 1 \le u,v \le n$，$u,v$ 在 $G_1$ 内连通充要于 $G_2$ 内连通。这一性质如果了解 最小生成树计数 的做法就不难看出。

知道这一点后，该如何设计出一个易于改写为计数的判断 $G'$ 是否合法的算法？设 $G_v$ 只保留 $G$ 内所有边权 $\le v$ 的边后得到的图，$G'_v$ 为 $G'$ 的某颗合法外向生成树只保留边权 $\le v$ 的边后得到的图。由于上述性质，$\forall v \in \Z$，$G'_v$ 一定形成与 $G_v$ 弱连通性一致的外向森林（外向树删去一些边后得到外向森林）。且从 $v \to v+1$，考虑 $G_{v+1}$ 的某个连通块是由一些 $G_v$ 的连通块合并而来，相应的 $G'_{v+1}$ 内点集一致的弱连通块一定由 $G'_v$ 内原来的对应的外向森林（设有 $s$ 颗外向树）合并而来，有恰 $s-1$ 个原来的外向树的根被一条 $G'$ 内边权为 $v+1$ 的边指向。

既然这样，不难看出实际上只有每个外向树的根是重要的。要对 $G'$ 找合法外向生成树，在固定 $v$ 时只需知道 $G_v$ 的每个连通块内，以这个连通块内的每个点为根是否存在满足上述过程的外向生成树。初始 $v=0$ 时 $G_0$ 没有边，所有点都合法。当 $v \to v+1$ 时，若 $G_{v+1}$ 合并了一些连通块 $S_1,S_2...S_k$ ，$u \in S_i$ 合法，当且仅当它之前就合法，且可以选出 $G$ 中一些权值为 $v+1$，指向的点也之前合法的边，使得将 $S_i$ 整体视作一个点后，选出的边在 $k$ 个点的图上是一颗以 $i$ 为根的外向树。最后只要有至少一个点合法 $G'$ 就合法。

新问题与 C 性质是非常类似的，但区别在于在新问题上即使是权值为 $v+1$ 的会被考虑的边，其也只在指向的点是之前合法的点时有意义。增量维护 $v$，设 $res_S$ 为 $S$ 所在的 $G_v$ 的连通块中 $S$ 恰是合法点集的概率，$res_S$ 的值仅在 $S$ 所有点在 $G_v$ 中属于同一连通块时才有意义。$v \to v+1$ 时需要计算新的 $res$，将 C 性质的做法移植过来即可，区别主要在于如果将一个 $G_v$ 中的连通块视作一个点的话，这个点带有一些 “属性” 是这个连通块之前的合法点集，而这个 “属性” 会影响转移系数（因为只有指向的点是合法点的边才有意义） 。细枝末节的地方建议 看代码。

最后是时间复杂度的问题，容易理解复杂度不会高于 $O(3^nn)$ 因为实际上连通性只会发生 $n$ 次合并，而每次合并的转移只是在做 C 性质是 $O(3^n)$ 的。但实际上加一个小优化：若点 $u$ 所在的连通块在 $G_v,G_{v+1}$ 中没有发生变化，所有包含 $u$ 的 $res$ 其实保持不变，于是所有包含 $u$ 的状态都无需考虑。那么合并总点数为 $s$ 的连通块便只消耗 $O(3^s)$ 时间，考虑 $T(n)=\max\limits_{a_1+a_2+a_3+...+a_k=n,a_i \ge 1,k > 1} (\sum\limits_{i=1}^k T(a_i)+O(3^n))$ 显然是 $O(3^n)$ 的。如果要分析得再仔细一些的话，上面给出的代码其实是 $O(2^nn^2+3^n)$ 的。