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$

### 约束条件 - $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 翻译