游戏match（【CCF】NOI Online能力测试2 提高组第三题 ）

1s 512M

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

作为旁观者的你只想知道，在他们随机选点的情况下，第一次非平局回合出现时的回合数的期望值。

为了计算这个期望，你决定对于 k=0,1,2,⋯,m，计算出非平局回合数为 k 的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 x，小 B 在 x 被小 A 选择的那个回合所选择的点不同。

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

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

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

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

共2/n +1 行每行一个整数，第 i 行的整数表示k=i−1 时的答案。
补充提示：
输出格式为一行2/n +1 个数或 2/n +1行每行一个数均可

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

0
10
10
4
0

涂色游戏color（【CCF】NOI Online 能力测试2 提高组第一题 ）
子序列问题sequence（【CCF】NOI Online能力测试2 提高组第二题 ）

match 测试