← 返回题目列表

Codeforces · 2028/E

E. 爱丽丝兔子洞历险记

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

爱丽丝在兔子洞的底部!兔子洞可以建模为一棵树$$$^{\text{*}}$$$,它在顶点$$$1$$$处有一个出口,而Alice从某个顶点$$$v$$$开始。她想要逃出深渊,但不幸的是,红心皇后下令处决她。

每分钟都会抛一枚公平的硬币。如果正面朝上,爱丽丝就可以移动到她当前位置的相邻顶点,否则,红心皇后可以将爱丽丝拉到皇后选择的相邻顶点。如果爱丽丝最终落在树的任何非根叶子$$$^{\text{†}}$$$上,爱丽丝就输了。

假设它们都以最佳方式移动,计算 Alice 对于每个起始顶点 $$$1\le v\le n$$$ 成功逃脱的概率。由于这些概率可能非常小,因此输出它们对 $$$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}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 树中的顶点数。

接下来的 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$ 和 $$$x_i \neq y_i$$$) — 树的边缘。保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,在一行上输出 $$$n$$$ 个整数 - Alice 从顶点 $$$1, 2, \ldots, n$$$ 开始逃逸的概率。由于这些概率可能非常小,因此输出它们对 $$$998\,244\,353$$$ 取模。

示例

输入 #1

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

输出 #1

1 499122177 499122177 0 0 
1 499122177 0 332748118 166374059 0 443664157 720954255 0

注意

对于第一个测试用例:

1. 根据定义,Alice 从根(顶点 $$$1$$$)逃脱,概率为 $$$1$$$。
2. Alice 立即从顶点 $$$4$$$ 和 $$$5$$$ 中失败,因为它们是叶子。
3. 从另外两个顶点,爱丽丝以 $$$\frac 12$$$ 的概率逃脱,因为女王会将她拉到叶子上。