Ammunition Dumps（code festival 2014 上海 [G]）

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

読解！

解法

問題文に書かれている、同一視の基準をよく読みます。$(a,b)$ を根とする全域有向木を数えればよいと分かります。

固定された根に対する全域有向木と、（根のない無向の）全域木は一対一に対応するので、全域木を数えればよいです（各建物から、上下左右に最寄りの建物に辺を張ります）。

あとは、グラフの接続行列を作って、Kirchhoff の行列木定理 を適用するだけです。