103145: [Atcoder]ABC314 F - A Certain Game

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$.

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

问题描述

$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}$。
• 然后，这两个队伍合并为一个队伍。

每场比赛的结果与其他比赛的结果无关。

对于每个玩家，输出在整个比赛期间，该玩家所在的队伍获胜的期望次数，对$998244353$取模。

约束条件

• $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$，即在整个比赛中，玩家$i$所在的队伍获胜的期望次数，对$998244353$取模，如下所示：

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

在整个比赛中，队伍$\lbrace 1, 2, 3, 4, 5 \rbrace$中玩家$1, 2, 3, 4, 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