Let the answer for a colour ~C~ be the number of sequences where ~C~ is completely removed from the tree in the shortest amount of time. Consider each colour ~C~ independently. We arbitrarily pick a root for the tree. This root will not be removed in the sequence of removals. Rooting the tree allows us to uniquely identify which subtrees need to be removed in an optimal removal, so we can compute the answers. Now, we want to try all possible roots which result in different optimal removals. To do this, we want to look at the subgraphs which do not contain any node of colour ~C~. If we remove all nodes with colour ~C~, this splits the graph into multiple subgraphs. For each subgraph, the answer will be the same wherever we root the tree. Therefore, we only need to try one root in each subgraph. Once we have all the answers for each possible root, we can find the answer for the whole tree.

Subtask 1

For each colour ~C~, we try rooting the tree in every subgraph formed by removing all nodes with colour ~C~. We then compute the answer for each root in ~\mathcal{O}(N)~ or ~\mathcal{O}(N \log MOD)~ with tree dp. Over all colours, the total amount of roots we have to try is ~\mathcal{O}(N)~.

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

Subtask 2

Now, say we initially rooted the tree at node ~R~ and computed the answers for all colours. When we try to move the root of the tree from ~R~ to a child of ~R~, notice that the only answer that changes is the answer for the colour of node ~R~, since we moved into a different subgraph. This means that at each node, we only need to update the answer for ~1~ colour. Thus, we can find the answers at all roots by rerooting the tree with dfs. This involves maintaining the last root encountered for each colour and returning info up the tree to those roots.

Time Complexity: ~\mathcal{O}(N \log MOD)~