Consider the root of the current subtree. Each of the children of the root is a root of another subtree. These children subtrees are independent of one another. This means that after we calculate the number of possible colorings F[i] for each subtree we have to count how many possible ways are there to merge all of the subtrees together such that the conditions are still satisfied:

F[i] = number of ways to color the subtree with root i.

At the current step we want to calculate F[x] where x is the root of the current subtree. At this step we already have all F[i] where i is a child of x. Initially F[x] = 1

Let N be the remaining positions we have to color. Initially N will be the size of the subtree rooted at x. We know that x has to be the first node to be colored, so we decrease N by one. Let S[i] be the size of the subtree rooted at the first children i of X:

F[x] = F[i] * C(N, S[i]). Why? We have N remaining valid positions we have to color. Of these remaining valid positions we need to choose S[i] positions to put all the nodes of subtree rooted at i and multiply the possible ways of choosing S[i] out of N by F[i] (possible ways to color subtree rooted at i). After this the remaining valid positions will be N = N — S[i] and we repeat the process for every remaining child: F[x] = F[x] * F[i] * C(N, S[i]) while always decreasing the number of valid positions.

This works because the only condition is that each node must be colored after its parent. It doesn't matter how many nodes come in between as long as at some point it will be colored and at that point the parent is already colored.