P5643 [PKUWC2018] 随机游走

给定一棵 $n$ 个结点的树，你从点 $x$ 出发，每次等概率随机选择一条与所在点相邻的边走过去。 有 $Q$ 次询问，每次询问给定一个集合 $S$，求如果从 $x$ 出发一直随机游走，直到点集 $S$ 中所有点都至少经过一次的话，期望游走几步。 特别地，点 $x$（即起点）视为一开始就被经过了一次。 答案对 $998244353 $ 取模。

无

无

对于 $20\%$ 的数据，有 $1\leq n,Q\leq 5$。 另有 $10\%$ 的数据，满足给定的树是一条链。 另有 $10\%$ 的数据，满足对于所有询问有 $k=1$。 另有 $30\%$ 的数据，满足 $1\leq n\leq 10 ,Q=1$。 对于 $100\%$ 的数据，有 $1\leq n\leq 18$，$1\leq Q\leq 5000$，$1\leq k\leq n$。