Let's begin by trying to find a DP solution to this problem:

We can define the DP state as follows:

Let ~dp[i]~ be the number of permutations of the nodes in the subtree of node ~i~ that satisfies the property Ridiculous Ray wants.

From this state, we can get the following recurrence:

Let ~s_1, s_2, \dots, s_k~ be the set of nodes adjacent to node ~i~.

Let ~sz[i]~ be the number of nodes in the subtree of node ~i~.

$$\displaystyle dp[i] = (sz[i]-1)! \cdot \prod_{i=0}^k \frac{dp[s_i]}{sz[s_i]!}$$

Observation: the resulting formula we get from expanding this recurrence on any tree will be a sequence of multiplications. Instead of storing the prime factorization of the overall answer, we can just count the number of times each integer occurs in the product and add its prime factorization ~f~ times to the answer (where ~f~ is its frequency).

Then, to optimize the solution to get full points, a difference array can be used as the answer is the product of ~\mathcal O(N)~ factorials.

The first subtask was meant to reward brute force solutions.

The second subtask was meant to reward contestants that found the recurrence but computed the DP values directly, either by storing the prime factorization as a map data structure or by using arbitrary precision integers.

Time complexity: ~\mathcal O(N \log N)~