The number of labeled tree is represented by the following Cayley’s formula:

• The number of \(N\)-vertex labeled tree is \(N^{N-2}\).

There are various ways to prove this; one is to use Prüfer code.

We omit the details, but in the idea of Prüfer code, we construct a bijection between \(N\)-vertex labeled trees and a sequence of \((N-2)\) integers between \(1\) and \(N\). Here, the number of occurrences of \(x\) in the obtained sequence equals the degree of vertex \(x\), subtracted by one.

Using that fact, the problem can be rephrased as follows.

How many sequences of \((N-2)\) integers between \(1\) and \(N\) are there such that \(i\) occurs \(S_1-1,S_2-1,\ldots\), or \(S_K-1\) times, for all \(i\ (1\leq i \leq N)\)?

This can be represented as \( (N-2)![x^{N-2}]f^{N}(x) \), where \(\displaystyle f(x)=\sum_{i=0}^\infty \frac{a_i}{i!}x^i\) is the exponential generating function of a sequence \(a\) such that \(i + 1 \in S \Rightarrow a_i = 1, i + 1 \notin S \Rightarrow a_i = 0\). This is derived from the multinomial theorem.

\(f^N(x)\) can be computed in a total of \(\mathrm{O}(N\log^2 N)\) with fast exponentiation and NTT (Number Theoretic Transform). With Newton’s method, exp and log can be computed in an \(O(N\log N)\) time, so \(f^N(x)\) can be computed in \(\mathrm{O}(N\log N)\) time too. Therefore, the problem has been solved.