[1] Double counting

Considering it from the leaves, there is a unique way, if any, to direct a tree to satisfy the condition. Thus, instead of undirected trees, let us count labeled directed trees where each vertex has the outdegree \(D_i\).

One method frequently used in counting trees with labeled vertices is double counting, which is applicable to this problem.

Let \(A\) be the answer to the problem, and \(B\) be the number of rooted trees where:

• the root may be any of the \(N\) vertices, and
• the \(D_i\) edges going out from each vertex \(i\) are labeled with integers from \(1\) to \(D_i\).

Then, \(B=A \times N \times \prod_{i=1}^{N} D_i !\), so finding \(B\) will also find \(A\).

[2] Construction of the rooted trees

The rooted trees can be constructed as follows. Additionally, for each of them, there is a unique way to construct it in this method.

• Decide a set \(S\) of vertices with an edge toward the root.
• For each \(i \in S\), choose from the \(D_i\) edges the one toward the root, and decide its ending vertex.
• Decide the ending vertices of the other edges.

Consider the number of ways to perform the third step after completing the first and second. Let us decide the ending vertex of the edges in ascending order of (the index of the starting vertex, the edge’s label). As the ending vertex, one can choose any vertex without a parent and outside the (weakly) connected component to which the edge belongs. Initially, there are \(N-|S|\) vertices without a parent, and this number decreases by \(1\) each time, so there are \((N-|S|-1)!\) ways to perform the third step. Particularly, this number is independent of the second step.

Next, consider the number of ways to perform the second step. There are \(\prod_{i \in S}D_i\) ways to choose the edges toward the root. For the number of ways to choose their ending vertices, observe that it equals the number of rooted forests with \(N\) labeled vertices and \(|S|\) edges such that the set of vertices with a parent is \(S\). For now, we will ignore the condition that the set of vertices with a parent should be \(S\). Let us start with \(N\) vertices and \(0\) edges and repeat the following \(|S|\) times to make a rooted forest: connect to a vertex \(u\) another vertex \(v\) without a parent and outside the connected component to which \(u\) belongs. There are \(\prod_{i=1}^{|S|} N \times (N-i)= N^{|S|} \times \frac{(N-1)!}{(N-|S|-1)!}\) ways to choose \(u\) and \(v\), and after removing duplicates that only differ by the order the edges are added, there are \(N^{|S|} \times \frac{(N-1)!}{|S|!(N-|S|-1)!}\) rooted forests that can be constructed. From symmetry, \(N^{|S|} \times \frac{(N-1)!}{|S|!(N-|S|-1)!} \times \frac{1}{{}_NC_{|S|}}=N^{|S|-1}(N-|S|)\) of them satisfy the condition that the set of vertices with a parent should be \(S\) (also for the case \(|S|=0\)).

Thus, for \(S\) fixed in the first step, there are \(N^{|S|-1} \times (N-|S|)! \times \prod_{i \in S}D_i\) rooted trees that can be constructed.

[3] Using convolution

Therefore, if we let \(f(x)=\prod_{i=1}^{N} (1+D_ix)\), we have \(B=\sum_{k=0}^{N-1} N^{k-1} (N-k) [x^k] f(x)\). One can find \(f(x)\) in \(O(N\log^2N)\) time by convoluting the factors in a manner resembling a complete binary tree. Alternatively, one can process the factors with the same \(D_i\) using binomial theorem and then convolute the results in descending order of \(D_i\) to find it in \(O(N\log N)\) time.