We will color each vertex black or white according to its parity.

Let’s consider the condition under which a rooted forest can be erased. (Assume that it may not be erased from the root direction.)

For each subtree \(t\), we calculate three values:

• \(white(t)\): the number of white vertices
• \(black(t)\): the number of black vertices
• \(best(t)\): how much this subtree can be minimized

\(best(t)\) is defined as follows: When we have \(t\) plus infinite isolated black vertices and infinite isolated white vertices, consider erasing this \(t\). Let’s assume that it is advantageous for the subsequent operations if many operations choose two vertices in \(t\). So, let’s minimize the number of operations that choose one vertex in \(t\) and one isolated vertex, and let \(best(t)\) be that minimum value.

Here, \(best(t)\) has the following properties:

• For any \(c=best(t),best(t)+2,\cdots,white(t)+black(t)\), there is a sequence of operations with exactly \(c\) operations that choose one vertex in \(t\) and one isolated vertex.
• Furthermore, there is always such a sequence of operations in the following form:
  • Assume without loss of generality that the root of the subtree is black.
  • Let \(a=max(white(t)-black(t),0)\) and \(b=max(black(t)-white(t),0)\).
  • The sequence of colors of the vertices chosen from the \(t\) side in the operations that choose one vertex in \(t\) and one isolated vertex is in the form W\(\times a+\)B\(\times b+\)WBWB\(\cdots\) (the total length is \(c\)). (If the root of the subtree was white, it ends with BWBW\(\cdots\))

By using this property, you can write a merge function for subtrees and find \(best(t)\) for each subtree with a tree DP. Also, by considering how the merges take place, you can confirm that the above properties hold.

Next, consider the condition under which rooted trees \(t_1,t_2,\cdots\) can be erased:

• The sum of \(white(t_i)\) and the sum of \(black(t_i)\) are equal.
• There is a tree whose root is white and a tree whose root is black.
• For every rooted tree \(t_i\), \(best(t_i) \leq \) (the total number of vertices in the other trees).

These are clearly necessary. Moreover, these are sufficient. This is because one can use the property of \(best(t_i)\) to make an appropriate sequence of operations.

Based on the above discussion, solve the counting by DP.

Consider the set of rooted subtrees to be erased in the end. Among these, fix the one with the maximum \(best\), and let this subtree be \(v-p\) (the subtree with \(v\) as the root when the parent of vertex \(v\) is set to \(p\)).

After that, we just need to count the number of ways to appropriately select a set of subtrees within the subtree \(p-v\) to satisfy the above conditions.

If you do this straightforwardly with DP, you need to find a table whose keys are the numbers of \(white\) and \(black\) vertices used for each subtree.

The computational complexity will be \(O(N^5)\) in total, which is fast enough because of small constant factors in various parts. (\(white \times black\) is small, the size of the subtree \(p-v\) is small on average, etc.)

Sample Implementation