题解：SHOI2016 黑暗前的幻想乡

问题本质

有 $n$ 个点，$n-1$ 个建筑公司

每个公司有一个可修建的边集 $E_i$

需要选择 $n-1$ 条边构成生成树

每条边必须由能修建它的公司修建，且每个公司恰好修一条边

求方案数（边集 + 分配方式）

核心思路：容斥原理 + 矩阵树定理

1. 矩阵树定理回顾 对于无向图 $G$，构造 $n \times n$ 的拉普拉斯矩阵 $L$：

$L_{ii}$ = 点 $i$ 的度数

$L_{ij}$ = $-$(边 $(i,j)$ 的条数) 生成树个数 = $L$ 去掉任意一行一列后的行列式

2. 容斥原理转化 原问题：每个公司恰好选一条边。

用容斥转化为：每个公司至多选一条边（可以选 0 条）。

设全集 $U$ = 所有生成树（不考虑公司限制）。

设 $A_i$ = "公司 $i$ 选了至少一条边" 的生成树集合。

我们要求的是 "每个公司恰好一条边" = 不在任何一个 $A_i$ 的补集中？ 不对，我们需要更准确的容斥。

正确容斥： 设 $S$ 表示那些不使用的公司集合（$S \subseteq {1,2,\dots,n-1}$）。

定义：

对于集合 $S$，我们只能使用 $S$ 的补集 $\overline{S}$ 中的公司的边。

设 $f(S)$ = 只用 $\overline{S}$ 中的公司的边构成的所有生成树的数量（一个公司可以提供多条边）。

那么根据容斥原理： 答案 = $\sum_{S \subseteq {1,\dots,n-1}} (-1)^{|S|} f(S)$

为什么：

设 $x_i$ = 公司 $i$ 在生成树中使用的边数。

我们要求 $x_1 = x_2 = \dots = x_{n-1} = 1$。

容斥：强制某些公司 $i \in S$ 的 $x_i = 0$（不使用），其他公司随意（$\ge 0$）。

由容斥公式，恰好每个为 1 的方案数 = \sum_{S} (-1)^{|S|} \text{(强制 S 中公司为 0 的方案数)}。

3. 计算 $f(S)$ 对于固定的 $S$：

允许使用的公司集合 = $\overline{S}$

将这些公司能修的所有边并起来，构成一个图 $G_S$

$f(S)$ = 图 $G_S$ 的生成树个数（用矩阵树定理计算）

注意：如果 $|\overline{S}| < n-1$（即允许使用的公司数少于 $n-1$），理论上可能也能形成生成树，这会在容斥中被正确处理。

4. 算法步骤 text 枚举 S（0 到 2^(n-1)-1）:
   1. 建图 G_S：包含所有公司 i ∉ S 的边
   2. 如果 G_S 的边数 < n-1，则 f(S) = 0
   3. 否则构造拉普拉斯矩阵 L
   4. 去掉第一行第一列，计算行列式 det (模 1e9+7)
   5. ans += (-1)^|S| * det 输出 ans
5. 时间复杂度 枚举 $2^{n-1}$ 个子集

每个子集构造矩阵 $O(n^2)$

计算行列式 $O(n^3)$

总复杂度 $O(2^{n-1} \cdot n^3)$

$n \le 17$，$2^{16} \times 17^3 \approx 2^{16} \times 5000 \approx 3 \times 10^8$，可过。