How to find all topological sortings of a special DAG in O(N^2)

I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.

https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum

Problem description:

Nikita has a family tree $T$ consisting of $N$ members number from $1$ to $N$. Each of the $N-1$ edges in the tree represents a directed relationship. Basically if there is an edge from member $A$ to $B$, it means $B$ was born before $A$. Now, Nikita knows that these $N$ members were born in last $M$ days and only $1$ person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the $N$ family members.

Since the required answer can be quite large, print it modulo $10^9+7$.

Editorial:

By now, you might have got the problem is all about finding the number of topological sortings in the randomly directed tree $T$.

Let randomly root the tree $T$ at any node say $1$. Lets calculate a $dp(i, j)$ denoting the number of topological sorts of subtree rooted at $i^{th}$ node such that $i^{th}$ node is placed at position. Assume that there are $X$ outgoing edges to the children from and $Y$ incoming edges. Note that all the $X$ children has to be placed on the left and all the $Y$ children has to be placed on the right side of $i^{th}$ in a valid topological sort.

Now lets calculate another $dp(i, j)$ for those $X$ nodes. Similiarly, we will do for $Y$ nodes. Here $dp(i, j)$ denotes the number of ways of filling $j$ spaces using topological sorts of subtrees rooted at $X_1, X_2, \cdots X_i$ such that $X_1, X_2, \cdots X_i$ is placed in $j$ spaces. Note that to compute this $dp$, we can use the $DP$ already calculated at these children nodes.

$$dp(i, j) = \sum_{1 \le k \le |S_i|} \left( nCr(j, k) \times dp(i-1, j-k) \times \sum_{1\le l \le k} DP(i, l) \right)$$

Note that this $\sum_{1\le l \le k} DP(i, l)$ is just a prefix sum and can be precomputed.

Now, for $X$ nodes basically you have computed

First, the problem is about counting, not finding, all the topological sorts (though it is still hard for general DAGs). Second, the constraint that the graph is a tree makes this problem much simpler.

Consider a node $n$ with $k$ children $n_1,\ldots,n_k$. Suppose the subtrees rooted by $n_1,\ldots,n_k$ are respectively $T_1,\ldots,T_k$, the sizes of $T_1,\ldots,T_k$ are respectively $s_1,\ldots,s_k$, and the numbers of topological sorts of the members in $T_1,\ldots,T_k$ are respectively $c_1,\ldots,c_k$, then the number of topological sorts of the members in the tree rooted by $n$ is

$$\frac{(n_1+\cdots+n_k)!}{n_1!n_2!\cdots n_k!}c_1c_2\cdots c_k.$$

Using the formula above, you can compute the number of topological sorts of the members in each subtree from bottom to top. This results in an $O(N^2)$ algorithm.

StackExchange Computer Science Q#97277, answer score: 2