次数の条件がついたなもり木のより善い数え方

CODE FESTIVAL 2017 Elimination Tournament (名前が長い！) の F 問題の想定解よりも善い解法です． atcoder.jp

以下の条件を満たすような $N$ 頂点の無向グラフは何通りあるか．(頂点は区別する)

グラフは単純で連結

頂点 $i$ の次数は $d_i$

$d_i$ の総和が $2(N-1)$ のとき(つまり，グラフが木のとき)，答えは $\frac{(N-2)!}{(d_1 - 1)!(d_2 - 1)! \cdots (d_N - 1)!}$ である．

では， $d_i$ の総和が $2N$ のとき(つまり，グラフが俗に言う「なもり木」*1のとき) はどうか？

想定解は $O(N^{3})$ ですが，実は $O(N^{2})$ で解くことができます．

Prüfer Code は，各要素が $1 \sim N$ のいずれかである長さ $N-2$ の数列です． $N^{N-2}$ 通りある Prüfer Code と $N$ 頂点のラベル付き無向木の間には，1対1対応が存在します．

木に対する Prüfer Code は，以下の操作を $N-2$ 回繰り返して得られる長さ $N-2$ の数列 $A_1, A_2, \cdots , A_{N-2}$ です．

$i$ 回目の操作とする．現在の葉のうち，最も番号の若いものを選ぶ(これを $v_i$ とおく)． $v_i$ と唯一隣接している頂点の番号を $A_i$ とし， $v_i$ を木から取り除く．

次のように考えると，Prüfer Code から木を復元できることがわかります．

$i$ 回目の操作における「現在の葉」がわかれば，そのうち最も番号の若いものが $v_i$ と判明します．
ここで，以前の操作で取り除いた頂点たち，つまり $v_1, \cdots, v_{i-1}$ は明らかに葉になりえません．また， $A_i, \cdots, A_{N-2}$ は現在の内点*2であり，逆に現在の内点はここに現れます(図を描いて確かめてみよう)．したがって， $v_1, \cdots, v_{i-1}, A_i, \cdots, A_{N-2}$ 以外の頂点が現在の葉です．
$i$ 回目の操作で取り除かれた辺は $2$ 頂点 $v_i, A_i$ を結ぶものです．全操作を終えた後は $2$ 頂点の木になるはずなので， $v_i$ として登場しなかった $2$ 頂点間に最後まで残った $1$ 辺があります．

たとえば，以下のグラフに対応する Prüfer Code は $4, 6, 2, 6$ です．

上の2つは互いに逆の操作になっています．あらゆる $p \in \{1, 2, \cdots, N\}^{N-2}$ に対して「復元」によって木が作れるので，1対1対応があるとわかりました．

Prüfer Code の考え方を応用します．

まずは木のときを確かめます．木の Prüfer Code において， $v$ の登場回数は $d_v - 1$ に等しいことから，木のときの問題は以下のように言い換えられます．

長さ $N-2$ の数列であって， $v$ が $d_v - 1$ 回現れるものは何通りか．

これは簡単に解けて，結果は問題概要にある通りになります．

これを参考に，なもり木における「Prüfer Code もどき」を以下のように定義します．

$v$ を $d_v - 1$ 個含む，長さ $2N$ の数列．
「Prüfer Code もどき」からのなもり木の復元は，以下のようにして行う．
- 残りの要素がuniqueでない間は，木のときと同様に「現在の葉」を求め，最も番号の若い葉と $A_i$ を辺でつなぐ操作を繰り返す．
- 残りの要素がuniqueになったら，残りの要素を円状に並べ，隣接する $2$ つの番号の頂点を辺でつなぐ．

たとえば， $6, 4, 5, 6, 2, 6, 1, 4$ という「Prüfer Code もどき」からは，以下のなもり木が復元されます．

わかりやすさのために，

閉路の長さが $L$ のなもり木のことを「 $L$ -なもり木」，
「Prüfer Code もどき」のうち
- 末尾 $L$ 要素がuniqueなものを「 $L$ -もどき」，
- uniqueな接尾辞の最大長が $L$ ，つまり " $L$ -もどき" だが " $(L+1)$ -もどき" ではないものを「ちょうど $L$ -もどき」