はじめに Cayley の公式、すなわち頂点ラベル付き木の個数が \(N^{N-2}\) 個であることを簡単に確認します。

こうした問題に対する典型的な母関数の立て方として、「木を 1 つ取ってきて、さらに 1 頂点を根とみなした通り数」の指数型母関数を考えます。これを \(F(x)\) とすると、

\[F(x) = x \exp(F(x)) \iff \frac{F(x)}{\exp(F(x))} = x\]

が成り立つため、反転して (反転については ABC345G 解説 を参照してください)

\[\left[\frac{x^N}{N!}\right] F(x) = N! \cdot \frac{1}{N} [x^{N-1}] \exp(x)^N = N^{N-1}\]

を得るため、最初に頂点を選んだ方法の \(N\) 通りで割った \(N^{N-2}\) が答えとなります。

\(K=1\) の場合

Cayley の公式の導出方法を踏まえて \(K = 1\) の場合を考えます。

• 「Alice (手番でない側)が勝つ木を 1 つ取ってきて、さらに 1 頂点を根とみなした通り数」の指数型母関数を \(A(x)\)、
• Bob (手番側)の場合の同様の指数型母関数を \(B(x)\)

とします。Bob が勝つ木は「子に手番でない側が勝つ木が存在するもの」で Alice はその逆です。よって

\[A = x \exp B\]

\[B = x (\exp(A+B) - \exp(B))\]

という式を得られます。1 本目の式を 2 本目に代入すると

\[B = x (\exp(x \exp B + B) - \exp(B))\]

という式を得られます。よって \(B\) のみからなる閉じた式 \(G(B) = 0\) を得られたことになるので、ニュートン法により \(B\) を計算することが出来てそこから \(A\) を計算できます。(ニュートン法についても ABC345G 解説 を参照してください) よってこの問題を \(\mathrm{O}(N \log N)\) で解くことが出来ます。

\(K=N\) の場合

\(K = N\) の場合、次の事実が成り立ちます。

グラフ上に完全マッチングが存在すれば Bob が勝ち、そうでない場合は Alice が勝つ。

(証明) 完全マッチングが存在する場合、完全マッチングを自由に取り \(M\) とします。そして、Alice による頂点 \(v\) への移動に対して Bob は \(v\) と \(M\) 上でマッチングしている頂点に移動するという戦略を取ります。この戦略は常に行動可能であることが証明できるため Bob はこれで負けません。
完全マッチングが存在しない場合、最大マッチングを自由に取り \(M\) とします。そして Alice は \(M\) に含まれない頂点を 1 個選びその頂点に移動します。その後、Bob による頂点 \(v\) への移動に対して Alice は \(v\) と \(M\) 上でマッチングしている頂点に移動するという戦略を取ります。この戦略は常に行動可能です。

• なぜならば行動不可能になった場合 \(u_0 - v_1 - u_1 - \dots - v_k - u_k - v_{k+1}\) というパスであって辺 \(v_i - u_i\) \((1 \leq i \leq k)\) が \(M\) に含まれて \(u_0, v_{k+1}\) が \(M\) に含まれないものが存在することになりますが、この場合 \(M\) から \(v_i - u_i\) \((1 \leq i \leq k)\) を取り除き \(u_i - v_{i+1}\) \((0 \leq i \leq k)\) を追加することで \(M\) よりサイズの大きいマッチングを取ることが出来るため \(M\) の最大性と矛盾するからです。

よって完全マッチングが存在しない場合、上記の戦略を取ることで Alice は負けません。以上より証明が完了しました。(証明終わり)

よって \(N\) が奇数の場合は Alice が常に勝ち、\(N\) が偶数の場合は完全マッチングが存在しない場合に Alice が勝ちます。Cayley の公式を踏まえると \(N\) が偶数の場合の完全マッチングを含む木の個数を数えられればよいです。
これは色々な方法で数えられます。例えば Cayley の公式の導出方法と同様に母関数を立てて反転公式を用いるのが一策です。適切な計算により完全マッチングを含む木の個数は \(\frac{N^{N/2-2} N!}{(N/2)!}\) であることが求められるので、答えを \(\mathrm{O}(N \log N)\) 程度で列挙できます。