Random Walk (Codeforces 1823F)
Tags: Math, probabilities

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:  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);  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: 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: 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}$$$.

Note: The tree from the first example is shown below:    Let's calculate expected value $$$E[c(1)]$$$:   $$$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.  As a result, $$$E[c(1)] = \sum\limits_{i=1}^{\infty}{i \frac{1}{2^i}} = 2$$$. Image of tree in second test   Image of tree in third test  

Sample Inputs:
3 1 3
1 2
2 3

4 1 3
1 2
2 3
1 4

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

Sample Outputs:
2 2 1

4 2 1 2

1 3 2 0 0 1 0 1

Solution (Python):
mod = 998244353
(n, s, t) = [int(x) for x in input().split()]
s -= 1
t -= 1
graph = [[] for x in range(n)]
for e in range(n - 1):
    (u, v) = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)
par = [-1 for x in range(n)]
q = []
q.append(t)
while len(q) > 0:
    i = q.pop()
    for j in graph[i]:
        if j != par[i] and par[j] == -1:
            par[j] = i
            q.append(j)
tot = [0 for x in range(n)]
x = s
while x != t:
    tot[x] = 1
    x = par[x]
q.append(t)
while len(q) > 0:
    i = q.pop()
    for j in graph[i]:
        if j != par[i]:
            tot[j] += tot[i]
            q.append(j)
for i in range(n):
    print(tot[i] * len(graph[i]) % mod if i != t else 1, end=' ')

Solution (Python):
from sys import setrecursionlimit
import threading
mod = 998244353

def main():
    (n, s, t) = map(int, input().split())
    s -= 1
    t -= 1
    g = [[] for i in range(0, n)]
    previous = [-1 for i in range(0, n)]
    inPath = [False for i in range(0, n)]
    res = [0 for i in range(0, n)]
    for i in range(0, n - 1):
        (a, b) = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    def dfs(v, p):
        for to in g[v]:
            if to == p:
                continue
            previous[to] = v
            dfs(to, v)

    def dfs2(v, p, k):
        res[v] = k * len(g[v])
        for to in g[v]:
            if to == p:
                continue
            dfs2(to, v, k)
    dfs(s, -1)
    ptr = t
    inPath[t] = True
    while ptr != s:
        res[previous[ptr]] = res[ptr] + 2
        ptr = previous[ptr]
        inPath[ptr] = True
    for v in range(0, n):
        if inPath[v]:
            res[v] = res[v] // 2 * len(g[v])
            for to in g[v]:
                if not inPath[to]:
                    dfs2(to, v, res[v] // len(g[v]))
    res[t] += 1
    for i in res:
        print(i % mod, end=' ')
    print('')
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()

Solution (Python):
from sys import setrecursionlimit
import threading
mod = 998244353

def main():
    (n, s, t) = map(int, input().split())
    s -= 1
    t -= 1
    g = [[] for i in range(0, n)]
    previous = [-1 for i in range(0, n)]
    inPath = [False for i in range(0, n)]
    res = [0 for i in range(0, n)]
    for i in range(0, n - 1):
        (a, b) = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    def dfs(v, p):
        for to in g[v]:
            if to == p:
                continue
            previous[to] = v
            dfs(to, v)

    def dfs2(v, p, k):
        res[v] = k * len(g[v])
        for to in g[v]:
            if to == p:
                continue
            dfs2(to, v, k)
    dfs(s, -1)
    ptr = t
    inPath[t] = True
    while ptr != s:
        res[previous[ptr]] = res[ptr] + 2
        ptr = previous[ptr]
        inPath[ptr] = True
    for v in range(0, n):
        if inPath[v]:
            res[v] = res[v] // 2 * len(g[v])
            for to in g[v]:
                if not inPath[to]:
                    dfs2(to, v, res[v] // len(g[v]))
    res[t] += 1
    for i in res:
        print(i % mod, end=' ')
    print('')
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()