[NOI Online #2 提高组]游戏

题目背景

1s 512M

题目描述

小 A 和小 B 正在玩一个游戏:有一棵包含 $n=2m$ 个点的有根树(点从 $1\sim n$ 编号),它的根是 $1$ 号点,初始时两人各拥有 $m$ 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点,若对手的点在自己的点的子树内,则该回合自己获胜;若自己的点在对方的点的子树内,该回合自己失败;其他情况视为平局。游戏共进行 $m$ 回合。 作为旁观者的你只想知道,在他们随机选点的情况下,第一次非平局回合出现时的回合数的期望值。 为了计算这个期望,你决定对于 $k=0,1,2,\cdots,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$ 时的答案。

输入输出样例

输入样例 #1

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

输出样例 #1

0
10
10
4
0

说明

| 测试点编号 | $n =$ | 特殊性质 | | :-- | :-- | :-- | | 1 $\sim$ 4 | $20$ | 无 | | 5 $\sim$ 8 | $50$ | 无 | | 9 $\sim$ 10 | $300$ | 树退化为一条链 | | 11 $\sim$ 12 | $300$ | 无 | | 13 $\sim$ 14 | $500$ | 无 | | 15 $\sim$ 16 | $5000$ | 树退化为一条链 | | 17 $\sim$ 20 | $5000$ | 无 |