Score : $475$ points

问题描述

设有 $N$ 名玩家，编号分别为 player $1$、player $2$、...、player $N$，参加一场游戏锦标赛。在比赛开始前，每位玩家各自组成一个单人队伍，因此总共有 $N$ 支队伍。

锦标赛共包含 $N-1$ 场比赛。每场比赛中，会选取两支不同的队伍进行对决。一支队伍先手，另一支队伍后手。每场比赛将会有且仅有一支队伍获胜。具体来说，对于每场第 $i = 1, 2, \ldots, N-1$ 的比赛，其过程如下：

• 拥有玩家 $p_i$ 的队伍先手，拥有玩家 $q_i$ 的队伍后手。
• 设第一队和第二队的队员人数分别为 $a$ 和 $b$，则第一队获胜的概率为 $\frac{a}{a+b}$，第二队获胜的概率为 $\frac{b}{a+b}$。
• 然后，两支队伍合并为一支队伍。

每场比赛的结果相互独立。

对于这 $N$ 名玩家中的每一位，请输出在整个锦标赛期间，该玩家所在队伍预期获胜的次数对 $998244353$ 取模后的结果。

如何打印模 $998244353$ 下的期望值

可以证明所求的期望值始终是理性的。同时，本问题的约束条件保证了如果所求期望值表示为不可约分数 $\frac{y}{x}$，则 $x$ 不会被 $998244353$ 整除。

现在存在一个唯一的整数 $z$，满足 $0 \le z \le 998244352$，且 $xz \equiv y \pmod{998244353}$。请报告这个 $z$ 值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

$N$ players, player $1$, player $2$, ..., player $N$, participate in a game tournament. Just before the tournament starts, each player forms a one-person team, so there are $N$ teams in total.

The tournament has a total of $N-1$ matches. In each match, two different teams are chosen. One team goes first, and the other goes second. Each match will result in exactly one team winning. Specifically, for each $i = 1, 2, \ldots, N-1$, the $i$-th match proceeds as follows.

• The team with player $p_i$ goes first, and the team with player $q_i$ goes second.
• Let $a$ and $b$ be the numbers of players in the first and second teams, respectively. The first team wins with probability $\frac{a}{a+b}$, and the second team wins with probability $\frac{b}{a+b}$.
• Then, the two teams are combined into a single team.

The result of each match is independent of those of the others.

For each of the $N$ players, print the expected number of times the team with that player wins throughout the tournament, modulo $998244353$.

How to print an expected value modulo $998244353$

It can be proved that the sought expected value is always rational. Also, the constraints of this problem guarantee that if the sought expected value is expressed as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998244353$.

Now, there is a unique integer $z$ between $0$ and $998244352$, inclusive, such that $xz \equiv y \pmod{998244353}$. Report this $z$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq p_i, q_i \leq N$
• Just before the $i$-th match, player $p_i$ and player $q_i$ belong to different teams.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$p_1$ $q_1$

$p_2$ $q_2$

$\vdots$

$p_{N-1}$ $q_{N-1}$

Output

For each $i = 1, 2, \ldots, N$, print $E_i$, the expected number, modulo $998244353$, of times the team with player $i$ wins throughout the tournament, separated by spaces, in the following format:

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

Sample Input 1

5
1 2
4 3
5 3
1 4

Sample Output 1

698771048 698771048 964969543 964969543 133099248

We call a team formed by player $x_1$, player $x_2$, $\ldots$, player $x_k$ as team $\lbrace x_1, x_2, \ldots, x_k \rbrace$.

• The first match is played by team $\lbrace 1 \rbrace$, with player $1$, and team $\lbrace 2 \rbrace$, with player $2$. Team $\lbrace 1 \rbrace$ wins with probability $\frac{1}{2}$, and team $\lbrace 2 \rbrace$ wins with probability $\frac{1}{2}$. Then, the two teams are combined into a single team $\lbrace 1, 2 \rbrace$.
• The second match is played by team $\lbrace 4 \rbrace$, with player $4$, and team $\lbrace 3 \rbrace$, with player $3$. Team $\lbrace 4 \rbrace$ wins with probability $\frac{1}{2}$, and team $\lbrace 3 \rbrace$ wins with probability $\frac{1}{2}$. Then, the two teams are combined into a single team $\lbrace 3, 4 \rbrace$.
• The third match is played by team $\lbrace 5 \rbrace$, with player $5$, and team $\lbrace 3, 4 \rbrace$, with player $3$. Team $\lbrace 5 \rbrace$ wins with probability $\frac{1}{3}$, and team $\lbrace 3, 4 \rbrace$ wins with probability $\frac{2}{3}$. Then, the two teams are combined into a single team $\lbrace 3, 4, 5 \rbrace$.
• The fourth match is played by team $\lbrace 1, 2 \rbrace$, with player $1$, and team $\lbrace 3, 4, 5 \rbrace$, with player $4$. Team $\lbrace 1, 2 \rbrace$ wins with probability $\frac{2}{5}$, and team $\lbrace 3, 4, 5 \rbrace$ wins with probability $\frac{3}{5}$. Then, the two teams are combined into a single team $\lbrace 1, 2, 3, 4, 5 \rbrace$.

The expected numbers of times the teams with players $1, 2, 3, 4, 5$ win throughout the tournament, $E_1, E_2, E_3, E_4, E_5$, are $\frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}$, respectively.

Sample Input 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

Sample Output 2

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

update @ 2024/3/10 08:59:19