问题2865--游戏(NOI Online2 lfw数据)

2865: 游戏(NOI Online2 lfw数据)

时间限制: 1 Sec  内存限制: 512 MB
提交: 4  解决: 4
[提交] [状态] [讨论版] [命题人:]

题目描述

小 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个字符为 0 表示i号点被小 A 拥有,否则被小 B 拥有。保证0、1的个数相同。
接下来n-1行每行两个正整数u, v,表示树中的一条边。

输出

共n/2+1行每行一个整数,第i行的整数表示k=i-1时的答案。

样例输入 Copy

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

样例输出 Copy

0
10
10
4
0

提示

1~4     n=20
5~8     n=50
9~10    n=300   树退化为一条链
11~12   n=300   无
13~14   n=500   无
15~16   n=5000  树退化为一条链
17~20   n=5000