[1] 有向木の数え上げ

初めに、良い木の個数を数えましょう。

良い木の個数は、根の次数が \(d_i\) 、それ以外の頂点の次数が \(d_i + 1\) であるような木の個数と一対一に対応しています。この数え上げは有名で（参考：ABC303-Ex ）、以下の形で書けます。

\[\displaystyle\frac{(N-2)!}{\prod (e_1(i) - 1)!}\]

　（便利のため、\(e_r(i)\) を \(i=r\) のとき \(e_r(i)=d_i\) 、\(i\neq r\) のとき \(e_r(i)=d_i+1\) を取る関数として定めています。）

[2] 主客転倒

頂点 \(v\) が良い頂点となるような木の個数を全ての頂点について足し合わせることで答えを求めます。\(v=1\) の場合や \(d_v=0\) の場合、 \(v\) は常に良い頂点なので単に良い木の個数を数えればよいです。以下 \(v\geq 2\) かつ \(d_v > 0\) の場合を考えます。

頂点 \(v\) の部分木に含まれる頂点集合を固定し、これを \(S\) とします。このとき、\(S\) については入次数と出次数の関係から \(\displaystyle\sum_{v\in S} d_v = |S| - 1\) が成り立つ必要があります。この関係が成り立つとき、良い木の個数は (\(S\) の要素からなる\(v\) の部分木の個数) \(\times\) (\(S\) に含まれない要素と \(v\) からなる木の個数) となることを用いると、[1] から以下のように書くことができます。

\[\displaystyle\frac{(|S|-2)!}{\prod_{i \in S} (e_v(i) - 1)!}\times \frac{(N-|S|+1 - 2)!}{\prod_{i \notin S} (e_1(i) - 1)!}\]

これを整理すると以下になります。

\[\displaystyle\frac{(|S|-2)!(N-|S|+1 - 2)!}{(d_1-1)! (d_v-1)!\prod_{i \neq 1, i\neq v} d_i!}=\displaystyle\frac{(|S|-2)!(N-|S| - 1)!d_1d_v}{ \prod d_i!}\]

[3] 動的計画法

[2] では \(S\) を決め打ちましたが、[2] で導出した式は \(v\) 及び \(|S|\) にしか依存しないことから、これは動的計画法でまとめて計算できます。具体的には、\(\mathrm{dp}[i][j][k]\) で頂点 \(N\) から頂点 \(i\) まで \(S\) の要素にするか決めて、出次数の和が \(j\) 、\(|S|=k\) であるような \(S\) の場合の数を管理すればよいです。

状態数が \(\mathrm{O}(N^3)\) 、遷移が \(\mathrm{O}(1)\) なので、結局 \(\mathrm{O}(N^3)\) でこの問題を解くことができます。