给你一棵由 $$$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}$$$。
第二次测试中的树图像
第三次测试中的树图像