Conquer or of Forest

Let’s strip the problem down to what actually matters: parity.

A non-root vertex is white iff the edge from its parent to it cuts off an even-sized component. So the operation is:

• choose an edge whose child-side component has even size,
• delete it,
• reconnect the two resulting components using any new cross edge.

The recoloring step is not magic; it just recomputes these parities.

Fixed Edges

Root the original tree at $1$. For every edge $(p, v)$ where $p$ is the parent of $v$, look at $sz[v]$.

If $sz[v]$ is odd, that edge is never removable.

Why? Suppose that edge is still present later. Other operations may move whole even-sized chunks across the area, but they only add/subtract even sizes from either side of this edge. Odd plus/minus even is still odd. So the side below that edge always has odd size whenever it is oriented away from the root. It never becomes a legal white cut.

So these odd-subtree edges are rigid. They are the bones of the tree.

Now delete every edge with even child-subtree size from the original tree. The remaining graph is a forest. Call its connected components blocks.

These blocks are fixed forever:

• edges inside blocks are never cut,
• every operation cuts only an edge between two blocks,
• every added edge also connects two blocks.

So the whole problem becomes a problem about rearranging a tree of blocks. The original labels inside each block still matter only because they give choices for endpoints.

Block Parities

Let the block containing vertex $1$ be the root block.

Every non-root block has even size. The root block has parity equal to $n$:

• if $n$ is odd, root block size is odd;
• if $n$ is even, root block size is even.

Every edge between blocks cuts off a union of non-root blocks, hence an even number of vertices. Therefore every block-tree edge is always legally cuttable. Nice: after compression, operations can rearrange the block tree basically however they want.

More precisely, all expanded spanning trees on the blocks are reachable. For an edge between block $a$ and block $b$, there are $s_a s_b$ possible real edges, where $s_i$ is the number of original vertices in block $i$.

When Is A Final Tree Conquered?

Inside a block, all internal child-subtree sizes are odd, so those vertices are black.

White vertices appear only at block entrances:

• for every non-root block, the vertex where the parent block connects into it is white;
• additionally, if $n$ is even, the root vertex is white, but it is obviously on every root path, so it causes no trouble.

Thus the conquered condition says:

all non-root blocks must lie on one root-to-some-block chain.

In other words, the contracted block tree must be a path whose one endpoint is the root block.

That is the whole damn problem.

Counting Weighted Rooted Paths

Suppose there are $m$ blocks. If $m=1$, no block edges exist, so the answer is $1$.

Otherwise, choose an ordering of all non-root blocks:

$$r, a_1, a_2, \dots, a_{m-1}$$

This represents the block path starting at the root block $r$.

For each adjacent pair $(x,y)$, we choose one actual vertex in block $x$ and one actual vertex in block $y$, giving $s_x s_y$ choices.

So this ordering contributes

$$(s_r s_{a_1})(s_{a_1}s_{a_2})\cdots(s_{a_{m-2}}s_{a_{m-1}}).$$

That product equals

$$s_r \cdot s_{a_{m-1}} \cdot \prod_{j=1}^{m-2} s_{a_j}^2.$$

So every middle non-root block contributes squared size, while the last block contributes only once.

Sum over the choice of the last block. The remaining $m-2$ blocks can be ordered arbitrarily, giving $(m-2)!$ orders.

Therefore:

$$ans = s_r \cdot (m-2)! \cdot \left(\prod_{i\ne r} s_i^2\right) \cdot \left(\sum_{i\ne r} \frac{1}{s_i}\right)$$

computed modulo $998244353$.

The modular inverses are valid because every block size is at most $n \le 2\cdot 10^5$, way below the modulus.

Algorithm

For each test case:

1. Root the tree at $1$ and compute subtree sizes.
2. DSU-merge every edge $(parent, child)$ with odd $sz[child]$.
3. Count the size of each resulting block.
4. Find the root block.
5. Apply the formula above.

Complexity is $O(n \alpha(n))$ per test case, basically linear.