Topcoder 10773 TheCitiesAndRoadDivOne 题解

观察“最少一条路径，最多两条路径”这个条件，发现图中至多有一个环，否则（有至少两个环）一定可以找一对点，使其间有至少 \(3\) 条路径。

1---2            1-2-3-4
 \ / \           | | | |
  3---4          5-6 7-8
(1与4间有3条路径)  (1与4间有4条路径)

所以图一定是棵树或者基环树。

树

先考虑树的情况。我们不要太着急上 Matrix Tree Theorem 之类的东西（有人是这样想的，其实本题根本用不到），先想想树是怎样构成的。树不就是在已给局面上一条一条加边加出来的嘛！

假定加边有顺序，那么每次都是从两个连通块里各挑一个点加边，合并两个连通块。

不难发现，只有每个连通块的大小是重要的；合并两个大小为 \(siz_1, siz_2\) 的连通块，方案数为 \(siz1 · siz2\) 。

可以大胆把“所有连通块大小的集合”设为状态，枚举其中两个进行转移，直到只剩一个连通块为止。乍一看很吓人，其实就算你不排序，状态数也只有 \(2^{num} - 1\) 个，更何况你还可以排序，将状态数减少到 \(num\) 的划分数。

最后由于加边其实是没有顺序的，你还要除以边数的阶乘 \((num - 1) !\) 。

基环树

考虑到本题 \(n \leq 20\) ，则 \(num \leq 20\) ，可以直接枚举 环跨越的连通块，然后合并它们，把问题转化回树的问题。

计算构成环本身的方案数有点烦。设跨越 \(k\) 个连通块，要分三种情况讨论：\(k = 1\), \(k = 2\), \(k > 2\)

\(k = 1\) 时，连通块 \(i\) 的方案数为：\(\frac{siz_i · (siz_i - 1)}{2} - (siz_i - 1)\) ，就是所有两端不相等的点对数量，减去距离恰好为 \(1\) （贴着一条边）的那些。

\(k = 2\) 时，连通块 \(i\) 与 \(j\) 的方案数为：\(\frac{e · (e - 1)}{2}\)，其中 \(e\) 为 \(i\) 与 \(j\) 间连一条边的方案数，即 \(siz_i · siz_j\) 。因为这个问题的实质是选两条不等的边，由于顺序问题还要除以 \(2\) 。

\(k > 2\) 时，设连通块集为 \(mask\)， \(mask\) 里的连通块首尾相连，顺序有 \(\frac{k!}{2}\) 种，连接方式有 \(siz_{ord_1} · siz_{ord_2} · siz_{ord_2} · siz_{ord_3} · ... · siz_{ord_k} · siz_{ord_1} = siz_{ord_1}^2 · siz_{ord_2}^2 · ... · siz_{ord_k}^2\) （其实和顺序没关系），乘起来就好。

汇总起来，终于解决了这道难题。