AT_abc314_f [ABC314F] A Certain Game

题目描述

有 $N$ 名玩家参加某个游戏比赛，分别为玩家 $1$、玩家 $2$、$\ldots$、玩家 $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}$ 的概率获胜。
• 比赛结束后，这两支队伍合并为一个队伍。

各场比赛的结果彼此独立。

请对于每位玩家 $i=1,2,\ldots,N$，输出其所在队伍在整个比赛期间获胜的次数的期望值 $E_i$，并对 $998244353$ 取模。

期望值 $\bmod\ 998244353$ 的定义：本题中要求的期望值一定是有理数。并且，在本题的约束下，若将期望值表示为最简分数 $\frac{y}{x}$，保证 $x$ 不会被 $998244353$ 整除。

此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$，满足 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入按以下格式从标准输入给出。

$N$ $p_1$ $q_1$ $p_2$ $q_2$ $\vdots$ $p_{N-1}$ $q_{N-1}$

输出格式

请按如下格式输出每位玩家 $i=1,2,\ldots,N$ 在整个比赛期间其所在队伍获胜次数的期望值 $E_i$（对 $998244353$ 取模），以空格分隔。

$E_1$ $E_2$ $\ldots$ $E_N$

输入输出样例 #1

输入 #1

5
1 2
4 3
5 3
1 4

输出 #1

698771048 698771048 964969543 964969543 133099248

输入输出样例 #2

输入 #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

说明/提示

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq p_i, q_i \leq N$
• 在第 $i$ 场比赛前，玩家 $p_i$ 所在队伍与玩家 $q_i$ 所在队伍不同。
• 输入均为整数。

样例解释 1

我们将包含玩家编号 $x_1, x_2, \ldots, x_k$ 的队伍称为队伍 $\lbrace x_1, x_2, \ldots, x_k \rbrace$。

• 第 $1$ 场比赛，玩家 $1$ 所在队伍 $\lbrace 1 \rbrace$ 与玩家 $2$ 所在队伍 $\lbrace 2 \rbrace$ 对战，以 $\frac{1}{2}$ 的概率队伍 $\lbrace 1 \rbrace$ 获胜，以 $\frac{1}{2}$ 的概率队伍 $\lbrace 2 \rbrace$ 获胜。之后两队合并为队伍 $\lbrace 1, 2 \rbrace$。
• 第 $2$ 场比赛，玩家 $4$ 所在队伍 $\lbrace 4 \rbrace$ 与玩家 $3$ 所在队伍 $\lbrace 3 \rbrace$ 对战，以 $\frac{1}{2}$ 的概率队伍 $\lbrace 4 \rbrace$ 获胜，以 $\frac{1}{2}$ 的概率队伍 $\lbrace 3 \rbrace$ 获胜。之后两队合并为队伍 $\lbrace 3, 4 \rbrace$。
• 第 $3$ 场比赛，玩家 $5$ 所在队伍 $\lbrace 5 \rbrace$ 与玩家 $3$ 所在队伍 $\lbrace 3, 4 \rbrace$ 对战，以 $\frac{1}{3}$ 的概率队伍 $\lbrace 5 \rbrace$ 获胜，以 $\frac{2}{3}$ 的概率队伍 $\lbrace 3, 4 \rbrace$ 获胜。之后两队合并为队伍 $\lbrace 3, 4, 5 \rbrace$。
• 第 $4$ 场比赛，玩家 $1$ 所在队伍 $\lbrace 1, 2 \rbrace$ 与玩家 $4$ 所在队伍 $\lbrace 3, 4, 5 \rbrace$ 对战，以 $\frac{2}{5}$ 的概率队伍 $\lbrace 1, 2 \rbrace$ 获胜，以 $\frac{3}{5}$ 的概率队伍 $\lbrace 3, 4, 5 \rbrace$ 获胜。之后两队合并为队伍 $\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}$。

由 ChatGPT 4.1 翻译