[1] double counting

葉側から考えると条件を満たすような向き付けは存在するならば一意です。よって条件を満たす木の代わりに各頂点の出次数が \(D_i\) であるようなラベル付き有向木を数えればいいです。

頂点ラベル付き木の数え上げでよく用いられる方法の \(1\) つに double counting があります。この問題でもこれを利用することができます。

この問題の答えを \(A\) とします。

• \(N\) 頂点のいずれかを根とする
• 頂点 \(i\) を始点とする \(D_i\) 本の辺に \(1\) から \(D_i\) までの整数でラベル付けがされている

ような根付き木の数を \(B\) とすると \(B=A \times N \times \prod_{i=1}^{N} D_i !\) なので \(B\) が求まれば \(A\) も求まります。

[2] 根付き木の構成

根付き木は以下の手順で構成できます。また、条件を満たす根付き木の以下での構成方法は一意に定まります。

• 根側に向かう辺をもつような頂点からなる集合 \(S\) を決める
• 各 \(i \in S\) について、根側に向かう辺を \(D_i\) 本の中から \(1\) 本選び、終点を決める
• 残りの辺について終点を決める

\(1,\ 2\) 番目の手順を終えた後、\(3\) 番目の手順としてありうるものの数を考えしょう。残りの辺の終点を (始点の頂点番号, 辺ラベル）の昇順に決めることにします。終点として選べるのは親頂点が存在しない頂点のうち、辺が属する（弱）連結成分の頂点以外すべてです。親頂点が存在しない頂点の数は、はじめ \(N-|S|\) 個で \(1\) 個ずつ減っていくので、\(3\) 番目の手順としてありうるのは \((N-|S|-1)!\) 通りです。とくにこれは \(2\) 番目の手順に依存していません。

つぎに \(2\) 番目の手順として考えられるものの数を考えます。根側に向かう辺の選び方は \(\prod_{i \in S}D_i\) 通りです。根側に向かう辺の終点の選び方ですが、これは \(N\) 頂点 \(|S|\) 辺の頂点ラベル付き根付き森のうち、親頂点が存在する頂点の集合が \(S\) であるようなものの数に等しいです。これについて「親頂点が存在する頂点の集合が \(S\) である」という条件を無視したものを考えます。\(N\) 頂点 \(0\) 辺からはじめて、いずれかの頂点 \(u\) と、親頂点が存在しない点 のうち \(u\) と連結成分が異なる頂点 \(v\)を選んで結ぶということを \(|S|\) 回繰り返して根付き森を作ることを考えます。\(u,\ v\) の選び方は \(\prod_{i=1}^{|S|} N \times (N-i)= N^{|S|} \times \frac{(N-1)!}{(N-|S|-1)!}\) 通りであり、辺が追加される順番による重複を除くと、構成できる根付き森は \(N^{|S|} \times \frac{(N-1)!}{|S|!(N-|S|-1)!}\) 通りです。 このうち「親頂点が存在する頂点の集合が \(S\) である」ものは対称性から \(N^{|S|} \times \frac{(N-1)!}{|S|!(N-|S|-1)!} \times \frac{1}{{}_NC_{|S|}}=N^{|S|-1}(N-|S|)\) 通りです（これは \(|S|=0\) の場合も正しいです）。

以上の議論から、\(1\) 番目の手順で \(S\) を固定した後、構成できる根付き木は \(N^{|S|-1} \times (N-|S|)! \times \prod_{i \in S}D_i\) 通りです。

[3] 畳み込みの利用

以上より \(f(x)=\prod_{i=1}^{N} (1+D_ix)\) とすると \(B=\sum_{k=0}^{N-1} N^{k-1} (N-k) [x^k] f(x)\) と求まります。 \(f(x)\) は二分木のように畳み込んでいくと \(O(N\log^2N)\) で求めることができます。また、同じ \(D_i\) については二項定理でまとめて処理し、\(D_i\) が大きいものから畳み込んでいくと \(O(N\log N)\) で求めることもできます。