Codeforces Beta Round #49 (Div. 2) E - Dead Ends
問題概要
$n$ 頂点 $m$ 辺の無向グラフ $G$ が与えられる。 $G$ の全域木であって、葉の個数が $k$ 個であるものは何通りか？
- $3 \le n \le 10$
- $\displaystyle n-1 \le m \le \frac{n(n-1)}{2}$
- $2 \le k \le n-1$
解法
まず、頂点集合 $S$ を固定し、「$S$ に含まれる頂点は葉でなくてはならない」という条件を満たす全域木の個数 $f(S)$ をすべての $S$ について求めることを考えます。
葉の次数は1なので、 $n \ge 3$ の条件から、葉同士を結ぶ辺はありません。
また、全域木から $S$ を除いたグラフも木になるということを考えると、まず $S$ 以外の頂点を連結にしてから、葉を接続するとしてよいことがわかります。
$S$ 以外の頂点だけを考えたときの全域木の個数は、行列木定理を用いれば $O(n^3)$ で求まります。
行列木定理を使わなくても、分割の方法を全通り試すDPを小さい方から計算すれば、 $O(n^2 3^n)$ ですべての頂点集合について前計算できます。(この場合、マージの順番が違うだけの同じ木を重複して数えないように注意が必要です。)
次に葉を接続する方法の数ですが、これは各葉について独立なので、簡単に求めることが出来ます。これで $f(S)$ をすべての $S$ について求められました。
この問題で求めたいのは、$T$のみが葉である全域木の個数 $g(T)$ です。これが求まれば、答えは $|T|=k$ となる $g(T)$ の総和として求められます。
$f(S)$ が $S \subseteq T$ となる $g(T)$ の総和であることを考えると、 $g(T)$ は包除原理から
\[
g(T)=\sum_{T \subseteq S} (-1)^{|S|-|T|}f(S)
\]
と計算できます。これは部分集合をそのまま計算しても全体で $O(3^n)$ で求められます。 高速メビウス変換を用いることで $O(n2^n)$ で計算することもできます。
(この問題には不要ですが)これをさらに高速化することもできます。 $f(S)$ の寄与を考えると
\[
\mathrm{ans} = \sum_{|T| = k} \sum_{T \subseteq S} (-1)^{|S|-|T|}f(S) = \sum_{T} (-1)^{|S|-|T|} \binom{|S|}{k} f(S)
\]
となることを用いて、$f$ の配列から $O(2^n)$ で直接答えを求めることができます。