← 返回题目列表

AtCoder · abc314_f

I. 某游戏

中文机器翻译题面 查看原题

分数: 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