← 返回题目列表

Codeforces · 1823/F

F. 随机游走

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 顶点和 $$$n - 1$$$ 边组成的树,每个顶点 $$$v$$$ 都有一个分配给它的计数器 $$$c(v)$$$。

最初,在顶点 $$$s$$$ 处放置一个筹码,并且除 $$$c(s)$$$ 之外的所有计数器均设置为 $$$0$$$; $$$c(s)$$$ 设置为 $$$1$$$。

您的目标是将芯片放置在顶点 $$$t$$$ 处。您可以通过一系列动作来实现它。假设现在芯片放置在顶点 $$$v$$$ 处。您只需一步执行以下操作:

1. 随机均匀地选择顶点 $$$v$$$ 的邻居 $$$to$$$ 之一(当且仅当树中存在边 $$$\{v, to\}$$$ 时,$$$to$$$ 是 $$$v$$$ 的邻居);
2. 将筹码移动到顶点$$$to$$$,并将$$$c(to)$$$增加$$$1$$$;

您将重复上述移动,直到到达顶点$$$t$$$。

对于每个顶点 $$$v$$$ 计算 $$$c(v)$$$ 模 $$$998\,244\,353$$$ 的期望值。

输入

第一行包含三个整数 $$$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$$$ 之间的边。

保证给定的边形成一棵树。

输出

打印 $$$n$$$ 数字:从 $$$1$$$ 到 $$$n$$$ 的每个 $$$v$$$ 的 $$$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$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

示例

输入 #1

3 1 3
1 2
2 3

输出 #1

2 2 1

输入 #2

4 1 3
1 2
2 3
1 4

输出 #2

4 2 1 2

输入 #3

8 2 6
6 4
6 2
5 4
3 1
2 3
7 4
8 2

输出 #3

1 3 2 0 0 1 0 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}$$$。

第二次测试中的树图像

第三次测试中的树图像