A Certain Game

题目描述

$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$ 取模。

输入格式

输入从标准输入按照以下格式给出： $N$ $p_1$ $q_1$ $p_2$ $q_2$ $\vdots$ $p_{N-1}$ $q_{N-1}$

输出格式

对于每个 $i = 1, 2, \ldots, N$，输出 $E_i$，即带有选手 $i$ 的队伍在整个锦标赛中获胜的期望次数对 $998244353$ 取模，数值间用空格分隔，格式如下： $E_1$ $E_2$ $\ldots$ $E_N$

5
1 2
4 3
5 3
1 4

698771048 698771048 964969543 964969543 133099248

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

43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq p_i, q_i \leq N$ 在第 $i$ 场比赛开始之前，选手 $p_i$ 和选手 $q_i$ 属于不同的队伍。 所有输入值均为整数。我们称由选手 $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}$。

标签: AtCoder|abc314F

来源

AtCoder|abc314F