P6478 [NOI Online #2 Senior] Game

1s 512M

Player A and Player B are playing a game. There is a rooted tree with $n = 2m$ nodes (nodes are numbered from $1 \sim n$). The root is node $1$. At the beginning, each player owns $m$ nodes. In each round, both players must choose one node that they own and that has not been chosen before. If the opponent’s chosen node is in the subtree of your chosen node, then you win this round. If your chosen node is in the subtree of the opponent’s chosen node, then you lose this round. In all other cases, the round is a draw. The game lasts for $m$ rounds in total. As a spectator, you only want to know, when they choose nodes uniformly at random, the expected round number at which the first non-draw round appears. To compute this expectation, you decide to compute, for $k = 0, 1, 2, \cdots, m$, the number of cases where the number of non-draw rounds is $k$. Two cases are considered different if and only if there exists a node $x$ owned by Player A such that, in the round where $x$ is chosen by Player A, the node chosen by Player B is different in the two cases. Since the total number of cases may be very large, you only need to output the result modulo $998244353$.

The first line contains a positive even integer $n$, denoting the number of nodes in the tree. The second line contains a 01 string of length $n$. The $i$-th character is $0$ if node $i$ is owned by Player A, otherwise it is owned by Player B. It is guaranteed that the number of $0$ and the number of $1$ are the same. The next $n - 1$ lines each contain two positive integers $u$, $v$, denoting an edge in the tree.

There are $\frac{n}{2} + 1$ lines in total, each containing one integer. The integer on the $i$-th line represents the answer when $k = i - 1$.

| Test Point ID | $n =$ | Special Property | | :-- | :-- | :-- | | 1 $\sim$ 4 | $20$ | None | | 5 $\sim$ 8 | $50$ | None | | 9 $\sim$ 10 | $300$ | The tree degenerates into a chain | | 11 $\sim$ 12 | $300$ | None | | 13 $\sim$ 14 | $500$ | None | | 15 $\sim$ 16 | $5000$ | The tree degenerates into a chain | | 17 $\sim$ 20 | $5000$ | None | Translated by ChatGPT 5