Consider the case where we must remove all edges from the tree. How many permutations can result from this? We should first note that the relative removal order of two edges which do not share an endpoint is irrelevant to the number of possible permutations. Next, note that the relative removal order of edges which share a common endpoint ~u~ always matters and that there are ~\deg[u]!~ ways to remove them (where ~\deg[u]~ is the number of edges incident to ~u~), each of these producing a distinct permutation (trivially proven by induction). Combining this observation over all nodes in the graph, we see that the total number of possible permutations is ~\prod_{u=1}^N \deg[u]!~. We now use this knowledge to devise solutions of various complexities.

Subtask 1

For this subtask, we may simply brute force over all subsets of edges to be removed, using the formula derived above to calculate the number of possible permutations for each subset.

Time Complexity: ~\mathcal{O}(N 2^N)~

Subtask 2

For a better complexity, we should consider using dynamic programming on a tree, rooting the tree at node ~1~. Our state is ~\text{dp}[i][j][k] :=~ the number of permutations of the subtree rooted at ~i~ if we remove ~j~ edges in this subtree (including the edge leading to the parent of ~i~), where ~k = 1~ iff we remove our parent edge. However, we should also keep track of the number of removed edges incident to ~i~ in order to multiply by ~\deg[i]!~ later, so our transition should be computed with an auxiliary DP where ~\text{dp2}[j][k] :=~ the number of permutations at node ~i~ if we remove ~j~ edges strictly in its subtree such that ~k~ of these connect ~i~ with a child of ~i~. Implemented naively, this algorithm runs in ~\mathcal{O}(N^4)~ time.

Time Complexity: ~\mathcal{O}(N^4)~

Subtask 3

We should now strive to optimize our algorithm from before. One such optimization comes from looping ~j~ up to only ~\text{sz}[v]~ when merging ~v~ with its parent, where ~\text{sz}[v]~ is the number of nodes in the subtree rooted at ~v~. This actually optimizes our code to ~\mathcal{O}(N^3)~, the proof of which is as follows:

Consider the set of nodes in our graph, initially with no edges. Each time we merge a node ~v~ with its parent, let's add an edge from all ~\text{sz}[v]~ nodes in the subtree of ~v~ to every other node in the subtree of any previously processed child of ~v~'s parent. Each edge represents a merge that we must process. In the end, the graph will become a complete graph with ~\mathcal{O}(N^2)~ edges, so we will be processing ~\mathcal{O}(N^2)~ merges in total. Since each merge is processed in ~\mathcal{O}(N)~, our proof is complete.

This technique can be applied to various other tree DP problems in order to optimize the complexity by a factor of ~N~.

Time Complexity: ~\mathcal{O}(N^3)~

Subtask 4

You may have realized that the modulus ~998\,244\,352~ is quite unusual. Why is that? Well, using any computational device at hand, we find that the prime factorization of ~998\,244\,352~ is ~2^{23} \cdot 7 \cdot 17~. This implies that ~x! \equiv 0 \pmod {998\,244\,352}~ for any ~x \ge 26~, which is actually highly useful for this particular problem. Specifically, this means that the ~k~ dimension in our auxiliary DP only needs to go up to ~25~; any higher and the product ~\prod_{u=1}^N \deg[u]!~ would just be congruent to ~0~, so there's no point in keeping track of it at all! Thus, our merges can now be processed in a constant amount of time instead of ~\mathcal{O}(N)~, bringing the total complexity down to ~\mathcal{O}(N^2)~.

Time Complexity: ~\mathcal{O}(N^2)~