CF2028E Alice's Adventures in the Rabbit Hole

爱丽丝在兔子洞的底部！兔子洞可以建模为一棵树 $^{\text{∗}}$ ，在顶点 $1$ 有一个出口，而爱丽丝从某个顶点 $v$ 开始。她想要逃出这个洞，但不幸的是，红心女王下令处决她。 每分钟都会抛一次公平的硬币。如果硬币正面朝上，爱丽丝可以移动到她当前位置的一个相邻顶点，否则，红心女王可以将爱丽丝拉到女王选择的一个相邻顶点。如果爱丽丝最终出现在树的任何非根叶子 $^{\text{†}}$ 上，爱丽丝就输了。 假设他们都以最佳方式移动，计算爱丽丝从每个起始顶点 $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}$ --- $^{\text{∗}}$ 一棵树是一个连通的简单图，具有 $n$ 个顶点和 $n-1$ 条边。 $^{\text{†}} $ 一个叶子是一个仅与一条边相连的顶点。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。测试用例的描述如下。 每个测试用例的第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$）——树中的顶点数量。 接下来的 $i$ 行中的第 $n - 1$ 行包含两个整数 $x_i$ 和 $y_i$ （$1 \le x_i, y_i \le n$ 和 $x_i \neq y_i$）——树的边。可以保证给定的边形成一棵树。 可以保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$ 。

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

对于第一个测试用例： 1.根据定义，爱丽丝从根节点（顶点 $1$）逃脱的概率为 $1$。\ 2.爱丽丝从顶点 $4$ 和 $5$ 立即输掉，因为它们是叶子。\ 3.从另外两个顶点，爱丽丝以概率 $\frac 12$ 逃脱，因为女王会将她拉到叶子。