Alice's Adventures in the Rabbit Hole
Contest: Codeforces Round 986 (Div. 2)
Difficulty rating: 2300
Tags: combinatorics, dfs and similar, dp, games, greedy, math, probabilities, trees

Alice is at the bottom of the rabbit hole! The rabbit hole can be modeled as a tree$$$^{\text{∗}}$$$ which has an exit at vertex $$$1$$$, and Alice starts at some vertex $$$v$$$. She wants to get out of the hole, but unfortunately, the Queen of Hearts has ordered her execution.

Each minute, a fair coin is flipped. If it lands heads, Alice gets to move to an adjacent vertex of her current location, and otherwise, the Queen of Hearts gets to pull Alice to an adjacent vertex of the Queen's choosing. If Alice ever ends up on any of the non-root leaves$$$^{\text{†}}$$$ of the tree, Alice loses.

Assuming both of them move optimally, compute the probability that Alice manages to escape for every single starting vertex $$$1\le v\le n$$$. Since these probabilities can be very small, output them modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the exact 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 < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of vertices in the tree.

The $$$i$$$-th of the next $$$n - 1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$ and $$$x_i \neq y_i$$$) — the edges of the tree. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output $$$n$$$ integers on one line — the probabilities of Alice escaping starting from vertex $$$1, 2, \ldots, n$$$. Since these probabilities can be very small, output them modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case:

1. Alice escapes from the root (vertex $$$1$$$) by definition with probability $$$1$$$.
2. Alice immediately loses from vertices $$$4$$$ and $$$5$$$ since they are leaves.
3. From the other two vertices, Alice escapes with probability $$$\frac 12$$$ since the Queen will pull her to the leaves.

Example input:
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

Example output:
1 499122177 499122177 0 0 
1 499122177 0 332748118 166374059 0 443664157 720954255 0

Editorial:
Note that Alice should always aim to move to the root, as this maximizes her probability of escaping (i.e., for any path from leaf to root, Alice's probability of escaping increases moving up the path). Furthermore, the Queen should always move downward for the same reason as above. Furthermore, the Queen should always move to the closest leaf in the subtree rooted at the current node.
There are now a few ways to compute this, but basically all of them are $$$O(n)$$$. For one such slick way, define $$$d(v)$$$ to be the distance to the closest leaf of the subtree of $$$v$$$, $$$p(v)$$$ to be the parent of $$$v$$$, and $$$t(v)$$$ to be the probability Alice gets the treasure starting at node $$$v$$$. Then, we claim that $$$t(v) = \frac{d(v)}{d(v)+1}\cdot t(p(v))$$$ for all vertices except the root. We can populate these values as we DFS down the tree.
Indeed, suppose that the tree is just a path with $$$d + 1$$$ vertices, labelled from $$$1$$$ through $$$d + 1$$$. Then, Alice's probability of getting the treasure at node $$$i$$$ is $$$1 - \frac{i - 1}{d}$$$ (this comes from solving a system of linear equations). This lines up with the above $$$t(v)$$$ calculation.
Now, we can construct the answer inductively. Let $$$P$$$ be a shortest root-to-leaf path in $$$T$$$ and consider the subtrees formed by removing the edges of $$$P$$$ from $$$T$$$. Each such subtree is rooted at some node $$$v\in P$$$. Then, in a subtree $$$T'$$$ rooted at $$$v$$$, the probability of Alice getting the treasure is exactly the probability that Alice gets to node $$$v$$$ and then to node $$$1$$$ from $$$v$$$, by the chain rule of conditioning and noting that the Queen will never re-enter the subtree $$$T'$$$ and the game will only play out along $$$P$$$ from this point forward. Therefore, it suffices to deconstruct $$$T$$$ into shortest root-to-leaf paths and note that at a given vertex $$$v$$$, we only have to play along the sequence of shortest root-to-leaf paths leading from $$$v$$$ to $$$1$$$. Along each of these paths, the above probability calculation holds, so we are done.