3400. [NOI Online 2020 2nd]游戏(民间数据)

【题目描述】

小 A 和小 B 正在玩一个游戏：有一棵包含 $n = 2m$ 个点的有根树（点从 $1\sim n$ 编号）,它的根是 1 号点，初始时两人各拥有 $m$ 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点，若对手的点在自己的点的子树内，则该回合自己获胜；若自己的点在对方的点的子树内，该回合自己失败；其他情况视为平局。游戏共进行 $m$ 回合。

作为旁观者的你只想知道，在他们随机选点的情况下，非平局回合数的期望值。为了计算这个期望，你决定对于 $k=0,1,2,\ldots,m$,计算出非平局回合数为 $k$ 的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 $x$ ,小 B 在 $x$ 被小 A 选择的那个回合所选择的点不同。

由于情况总数可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

【输入格式】

第一行一个正整偶数 $n$ 表示树的结点数

第二行一个长度为 $n$ 的 01 字符串，第 $i$ 个字符为 0 表示 $i$ 号点被小 A 拥有，否则被小 B 拥有。保证0、1的个数相同。

接下来 $n-1$ 行每行两个正整数 $u,v$,表示树中的一条边。

【输出格式】

共一行以空格隔开的 $\frac{n}{2}+1$ 个整数，第 $i$ 个整数表示 $k=i-1$ 时的答案。

【样例输入】

8
10010011
1 2
1 3
2 4
2 5
5 6
3 7
3 8

【样例输出】

0 10 10 4 0

【提示】

【来源】

NOI Online2020 提高组 第二轮 Task 3