P5643 [PKUWC2018] Random Walk

Given a tree with $n$ nodes, you start from node $x$. Each time, you randomly choose an edge adjacent to the current node with equal probability and walk along it. There are $Q$ queries. In each query, you are given a set $S$. Starting from $x$, you keep doing the random walk until every node in $S$ has been visited at least once. Find the expected number of steps. In particular, node $x$ (the starting node) is considered to have been visited once at the beginning. Output the answer modulo $998244353$.

The first line contains three positive integers $n, Q, x$. The next $n - 1$ lines each contain two positive integers $(u, v)$ describing an edge of the tree. The next $Q$ lines describe the queries. Each line starts with an integer $k$ denoting the size of the set, followed by $k$ pairwise distinct integers denoting the set $S$.

Output $Q$ lines. Each line contains a non-negative integer representing the answer.

For $20\%$ of the testdata, $1 \leq n, Q \leq 5$. For another $10\%$ of the testdata, the given tree is a chain. For another $10\%$ of the testdata, for all queries $k = 1$. For another $30\%$ of the testdata, $1 \leq n \leq 10$ and $Q = 1$. For $100\%$ of the testdata, $1 \leq n \leq 18$, $1 \leq Q \leq 5000$, and $1 \leq k \leq n$. Translated by ChatGPT 5