分数: 475 点
问题陈述
N 玩家,玩家 1,玩家 2, ..., 玩家 N,参加游戏锦标赛。比赛开始前,每个选手组成一个人的队伍,所以有 总共 N 支队伍。
比赛共有 N-1 匹配。每场比赛都会选择两支不同的球队。一队先行,另一队居第二。每场比赛都会有一支球队获胜。具体来说,对于每个 i = 1, 2, \ldots, N-1, i第场比赛进行如下。
- 拥有玩家的队伍 p_i 先行,有玩家的队伍 q_i 位居第二。
- 让 a 和 b 分别是第一队和第二队的球员人数。第一队获胜的概率 \frac{a}{a+b},第二队获胜的概率 \frac{b}{a+b}.
- 然后,两个团队合并为一个团队。
每场比赛的结果与其他比赛的结果无关。
对于每个 N 球员,打印该球员所在球队在整个比赛中获胜的预期次数,模数 998244353.
如何打印期望值模 998244353
可以证明,所求的期望值总是有理数。此外,该问题的约束保证如果所寻求的期望值表示为不可约分数 \frac{y}{x},那么 x 不能被整除 998244353.
现在,有一个唯一的整数 z 之间 0 和 998244352,包含在内,这样 xz \equiv y \pmod{998244353}。报告此事 z.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq p_i, q_i \leq N
- 就在之前 i第场比赛,玩家 p_i 和玩家 q_i 属于不同的团队。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
p_1 q_1
p_2 q_2
\vdots
p_{N-1} q_{N-1}
输出
对于每个 i = 1, 2, \ldots, N,打印 E_i,预期数字,模数 998244353,与玩家的团队次数 i 在整个锦标赛中获胜,以空格分隔,格式如下:
E_1 E_2 \ldots E_N
示例输入 1
5 1 2 4 3 5 3 1 4
示例输出 1
698771048 698771048 964969543 964969543 133099248
我们称由玩家组成的团队 x_1,玩家 x_2, \ldots,玩家 x_k 作为团队 \lbrace x_1, x_2, \ldots, x_k \rbrace.
- 第一场比赛由球队进行 \lbrace 1 \rbrace,与玩家 1和团队 \lbrace 2 \rbrace,与玩家 2。团队 \lbrace 1 \rbrace 有概率获胜 \frac{1}{2}和团队 \lbrace 2 \rbrace 有概率获胜 \frac{1}{2}。然后,两个团队合并为一个团队 \lbrace 1, 2 \rbrace.
- 第二场比赛由队伍进行 \lbrace 4 \rbrace,与玩家 4和团队 \lbrace 3 \rbrace,与玩家 3。团队 \lbrace 4 \rbrace 有概率获胜 \frac{1}{2}和团队 \lbrace 3 \rbrace 有概率获胜 \frac{1}{2}。然后,两个团队合并为一个团队 \lbrace 3, 4 \rbrace.
- 第三场比赛由队伍进行 \lbrace 5 \rbrace,与玩家 5和团队 \lbrace 3, 4 \rbrace,与玩家 3。团队 \lbrace 5 \rbrace 有概率获胜 \frac{1}{3}和团队 \lbrace 3, 4 \rbrace 有概率获胜 \frac{2}{3}。然后,两个团队合并为一个团队 \lbrace 3, 4, 5 \rbrace.
- 第四场比赛由队伍进行 \lbrace 1, 2 \rbrace,与玩家 1和团队 \lbrace 3, 4, 5 \rbrace,与玩家 4。团队 \lbrace 1, 2 \rbrace 有概率获胜 \frac{2}{5}和团队 \lbrace 3, 4, 5 \rbrace 有概率获胜 \frac{3}{5}。然后,两个团队合并为一个团队 \lbrace 1, 2, 3, 4, 5 \rbrace.
球队与球员的预期次数 1, 2, 3, 4, 5 在整个比赛中获胜, E_1, E_2, E_3, E_4, E_5,是 \frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}。
示例输入 2
15 9 2 8 10 13 6 12 11 7 10 4 10 14 2 5 4 1 15 15 2 6 9 8 11 6 3 2 8
示例输出 2
43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290