CF1823F.Random Walk

You are given a tree consisting of $n$ vertices and $n - 1$ edges, and each vertex $v$ has a counter $c(v)$ assigned to it.

Initially, there is a chip placed at vertex $s$ and all counters, except $c(s)$, are set to $0$; $c(s)$ is set to $1$.

Your goal is to place the chip at vertex $t$. You can achieve it by a series of moves. Suppose right now the chip is placed at the vertex $v$. In one move, you do the following:

1. choose one of neighbors $to$ of vertex $v$ uniformly at random ($to$ is neighbor of $v$ if and only if there is an edge ${v, to}$ in the tree);
2. move the chip to vertex $to$ and increase $c(to)$ by $1$;

You'll repeat the move above until you reach the vertex $t$.

For each vertex $v$ calculate the expected value of $c(v)$ modulo $998\,244\,353$.

你被给定一棵包含 $n$ 个顶点和 $n - 1$ 条边的树，且每个顶点 $v$ 都关联一个计数器 $c(v)$。

初始时，一枚棋子被放置在顶点 $s$ 上，除 $c(s)$ 被设为 $1$ 外，其余所有计数器均设为 $0$。

你的目标是将棋子移动至顶点 $t$。你可以通过一系列操作实现该目标。假设当前棋子位于顶点 $v$，则一次操作按如下步骤进行：

1. 在顶点 $v$ 的所有邻居 $to$ 中均匀随机选择一个（即：当且仅当树中存在边 $\{v, to\}$ 时，$to$ 是 $v$ 的邻居）；
2. 将棋子移至顶点 $to$，并将 $c(to)$ 的值增加 $1$；

你将重复上述操作，直至棋子到达顶点 $t$。

对每个顶点 $v$，计算其计数器 $c(v)$ 的期望值，并对 $998\,244\,353$ 取模。

The first line contains three integers $n$, $s$ and $t$ ($2 \le n \le 2 \cdot 10^5$; $1 \le s, t \le n$; $s \neq t$) — number of vertices in the tree and the starting and finishing vertices.

Next $n - 1$ lines contain edges of the tree: one edge per line. The $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \neq v_i$), denoting the edge between the nodes $u_i$ and $v_i$.

It's guaranteed that the given edges form a tree.

第一行包含三个整数 $n$、$s$ 和 $t$（$2 \le n \le 2 \cdot 10^5$；$1 \le s, t \le n$；$s \neq t$），分别表示树中顶点的数量、起点和终点。

接下来的 $n - 1$ 行描述树的边：每行一条边。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$；$u_i \neq v_i$），表示节点 $u_i$ 与 $v_i$ 之间存在一条边。

保证所给的边构成一棵树。

Print $n$ numbers: expected values of $c(v)$ modulo $998\,244\,353$ for each $v$ from $1$ to $n$.

Formally, let $M = 998\,244\,353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

输出 $n$ 个数：对每个 $v$（从 $1$ 到 $n$），输出 $c(v)$ 的期望值对 $998\,244\,353$ 取模的结果。

形式化地，令 $M = 998\,244\,353$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

The tree from the first example is shown below:

Let's calculate expected value $E[c(1)]$:

• $P(c(1) = 0) = 0$, since $c(1)$ is set to $1$ from the start.
• $P(c(1) = 1) = \frac{1}{2}$, since there is the only one series of moves that leads $c(1) = 1$. It's $1 \rightarrow 2 \rightarrow 3$ with probability $1 \cdot \frac{1}{2}$.
• $P(c(1) = 2) = \frac{1}{4}$: the only path is $1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 3$.
• $P(c(1) = 3) = \frac{1}{8}$: the only path is $1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 3$.
• $P(c(1) = i) = \frac{1}{2^i}$ in general case.

As a result, $E[c(1)] = \sum\limits_{i=1}^{\infty}{i \frac{1}{2^i}} = 2$.

Image of tree in second test

Image of tree in third test

第一个示例中的树如下所示：

我们来计算期望值 $E[c(1)]$：

• $P(c(1) = 0) = 0$，因为 $c(1)$ 从初始时刻起就被设为 $1$。
• $P(c(1) = 1) = \frac{1}{2}$，因为仅存在一条导致 $c(1) = 1$ 的操作序列：$1 \rightarrow 2 \rightarrow 3$，其概率为 $1 \cdot \frac{1}{2}$。
• $P(c(1) = 2) = \frac{1}{4}$：唯一路径为 $1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 3$。
• $P(c(1) = 3) = \frac{1}{8}$：唯一路径为 $1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 3$。
• 一般情况下，$P(c(1) = i) = \frac{1}{2^i}$。

因此，$E[c(1)] = \sum\limits_{i=1}^{\infty}{i \frac{1}{2^i}} = 2$。

第二个测试用例中的树图：

第三个测试用例中的树图：