コーナーケース

握手定理という有名な性質から、次数和が \(2(N-1)\) ではない場合、そのような木は存在しないため、答えは \(0\) です。

解法

想定解ではないですが、より一般の場合に解ける方法を紹介します。

このように次数が指定されたときの数え上げには Prüfer 列が効きます。Prüfer 列とは、\(n\) 頂点からなるラベル付き木と \(\{1,2,\cdots, n\}^{n-2}\) との一対一対応です。特に、 \(n\) 頂点からなるラベル付き木はちょうど \(n^{n-2}\) 個あります（これは Cayley の公式と呼ばれます）

性質として、各頂点 \(v\) について、(木の Prüfer 列に現れる \(v\) の個数) + 1 が、頂点 \(v\) の次数となります。Prüfer 列の定義や他の性質はここでは紹介しませんが、次の記事などが参考になります。

Prüfer sequence - 忘れても大丈夫 https://kyopro.hateblo.jp/entry/2019/01/16/200456

すべての頂点の次数が指定されたとき、Prüfer 列に現れるべき各値の出現回数は固定されているので、あとは並び替えを数えるだけです。

よって、求めるべき答えは、 \(a_i=k\) の個数を \(c_k\) としたとき、

\[\frac{(N-2)!}{0!^{c_1} 1!^{c_2} 2!^{c_3}} = \frac{(N-2)!}{2^{c_3}}\]

です。

Prüfer 列は意外にも競技プログラミングでの出題例が多くあります。たとえば、この問題の類題としては次のABCの問題があります。

https://atcoder.jp/contests/abc303/tasks/abc303_h