Random Walk
Contest: Codeforces Round 868 (Div. 2)
Difficulty rating: 2600
Tags: dp, graphs, math, probabilities, trees

You are given a tree consisting of $$$n$$$ vertices and $$$n - 1$$$ edges, and each vertex $$$v$$$ has a counter $$$c(v)$$$ assigned to it.

Initially, there is a chip placed at vertex $$$s$$$ and all counters, except $$$c(s)$$$, are set to $$$0$$$; $$$c(s)$$$ is set to $$$1$$$.

Your goal is to place the chip at vertex $$$t$$$. You can achieve it by a series of moves. Suppose right now the chip is placed at the vertex $$$v$$$. In one move, you do the following:

1. choose one of neighbors $$$to$$$ of vertex $$$v$$$ uniformly at random ($$$to$$$ is neighbor of $$$v$$$ if and only if there is an edge $$$\{v, to\}$$$ in the tree);
2. move the chip to vertex $$$to$$$ and increase $$$c(to)$$$ by $$$1$$$;

You'll repeat the move above until you reach the vertex $$$t$$$.

For each vertex $$$v$$$ calculate the expected value of $$$c(v)$$$ modulo $$$998\,244\,353$$$.

Input format:
The first line contains three integers $$$n$$$, $$$s$$$ and $$$t$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le s, t \le n$$$; $$$s \neq t$$$) — number of vertices in the tree and the starting and finishing vertices.

Next $$$n - 1$$$ lines contain edges of the tree: one edge per line. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$), denoting the edge between the nodes $$$u_i$$$ and $$$v_i$$$.

It's guaranteed that the given edges form a tree.

Output format:
Print $$$n$$$ numbers: expected values of $$$c(v)$$$ modulo $$$998\,244\,353$$$ for each $$$v$$$ from $$$1$$$ to $$$n$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the 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}$$$.

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

Note:
The tree from the first example is shown below:

- $$$P(c(1) = 0) = 0$$$, since $$$c(1)$$$ is set to $$$1$$$ from the start.
- $$$P(c(1) = 1) = \frac{1}{2}$$$, since there is the only one series of moves that leads $$$c(1) = 1$$$. It's $$$1 \rightarrow 2 \rightarrow 3$$$ with probability $$$1 \cdot \frac{1}{2}$$$.
- $$$P(c(1) = 2) = \frac{1}{4}$$$: the only path is $$$1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 3$$$.
- $$$P(c(1) = 3) = \frac{1}{8}$$$: the only path is $$$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}$$$ in general case.

Image of tree in second test

Image of tree in third test

Example input:
3 1 3
1 2
2 3

Example output:
2 2 1

Example input:
4 1 3
1 2
2 3
1 4

Example output:
4 2 1 2

Editorial:
Let $$$deg(v)$$$ be the number of neighbors of vertex $$$v$$$. Let's fix a vertex $$$v$$$ and its neighboring vertices $$$c_1, \dots, c_{deg(v)}$$$. According to the linearity of the expected values: $$$$$$e_v = \sum_{u \in \{c_1, \dots, c_{deg(v)}\}} \frac{e_u}{deg(u)}$$$$$$ This gives the system of equations, which, however, cannot be directly solved.
Solution by Igor_Parfenov:
Let's solve the subproblem: given a bamboo with vertices numbered in order from $$$1$$$ to $$$n$$$, and $$$s = 1$$$ and $$$t = n$$$. It is easy to see that the equation is satisfied by the expected values $$$\{n - 1, 2 \cdot (n - 2), 2 \cdot (n - 3), \dots , 6, 4, 2, 1\}$$$.
Now let's solve the problem. Consider the path from $$$s$$$ to $$$t$$$ (it is the only one in the tree). The chip must go through it, but at the vertices of the path, it can go to third-party vertices. Let us represent a tree as non-intersecting trees whose roots are vertices lying on the path from $$$s$$$ to $$$t$$$, and all other vertices do not lie on this path. Let's place the numbers $$$\{n - 1, n - 2, \dots, 2, 1, 0\}$$$ at the vertices of the path. Let's now fix a tree rooted at vertex $$$v$$$ in the path, and let its number be equal to $$$x$$$. Then we can see that the equation is satisfied by the values of the mathematical expectation $$$e_u = x \cdot deg(u)$$$. Separately, you need to make $$$e_t = 1$$$.
Solution by adedalic:
Let's take a path from $$$s$$$ to $$$t$$$ and call it $$$r_0, r_1, \dots, r_k$$$, where $$$r_0 = s$$$ and $$$r_k = t$$$. Now we will assume that each of the vertices $$$r_i$$$ form its own rooted subtree. Consider a leaf $$$v$$$ in an arbitrary subtree: $$$e_v = \frac{1}{deg(p)} e_p$$$, where $$$p$$$ is the ancestor of $$$v$$$.
Now, by induction on the subtree size, we prove that for any vertex $$$v$$$ in any subtree $$$r_i$$$ the expected value is $$$e_v = \frac{deg(v)}{deg(p)} e_p$$$. For the leafs, it's obvious. Further, by the inductive hypothesis: $$$$$$ e_v = \sum_{to \neq p}{\frac{1}{deg(to)} e_{to}} + \frac{1}{deg(p)} e_p = \sum_{to \neq p}{\frac{deg(to)}{deg(to) \cdot deg(v)} e_v} + \frac{1}{deg(p)} e_p = \frac{deg(v) - 1}{deg(v)} e_v + \frac{1}{deg(p)} e_p $$$$$$ $$$$$$ \frac{1}{deg(v)} e_v = \frac{1}{deg(p)} e_p \leftrightarrow e_v = \frac{deg(v)}{deg(p)} e_p$$$$$$.
Now consider the vertices on the path: $$$$$$e_{r_0} = 1 + \sum_{to \neq r_1}{\frac{1}{deg(to)} e_{to}} + \frac{1}{deg(r_1)} e_{r_1} = 1 + \frac{deg(r_0) - 1}{deg(r_0)} e_{r_0} + \frac{1}{deg(r_1)} e_{r_1} $$$$$$ $$$$$$ e_{r_0} = deg(r_0) \left( 1 + \frac{1}{deg(r_1)} e_{r_1} \right) $$$$$$
$$$$$$ e_{r_1} = \frac{1}{deg(r_0)} e_{r_0} + \sum_{to \neq r_0; to \neq r_2}{\frac{1}{deg(to)} e_{to}} + \frac{1}{deg(r_2)} e_{r_2} = \left( 1 + \frac{1}{deg(r_1)} e_{r_1} \right) + \frac{deg(r_1) - 2}{deg(r_1)} e_{r_1} + \frac{1}{deg(r_2)} e_{r_2}$$$$$$ $$$$$$ e_{r_1} = deg(r_1) \left( 1 + \frac{1}{deg(r_2)} e_{r_2} \right) $$$$$$ And so on. For $$$r_{k - 1}$$$ we get: $$$$$$ e_{r_{k-1}} = deg(r_{k-1}) \left( 1 + 0 \right) = deg(r_{k - 1}) $$$$$$ Now let's expand: $$$$$$ e_{r_{k-2}} = deg(r_{k-2}) \left( 1 + \frac{1}{deg(r_{k-1})} e_{r_{k-1}} \right) = deg(r_{k-2}) (1 + 1) = 2 \cdot deg(r_{k-2}) $$$$$$ $$$$$$ e_{r_{k-3}} = deg(r_{k-2}) \left( 1 + 2 \right) = 3 \cdot deg(r_{k-2}) $$$$$$ $$$$$$ e_{r_{k-i}} = i \cdot deg(r_{k-i}) $$$$$$
That's all. For any vertex $$$v$$$ in the subtree of $$$r_i$$$ we get $$$e_v = (k - i) \cdot deg(v)$$$.