P5643

# P5643 [PKUWC2018]随机游走 [洛谷：P5643 [PKUWC2018]随机游走](https://www.luogu.com.cn/problem/P5643) ## Solution 对点集 $S$，记 $\max(S)$ 表示将 $S$ 中所有点都遍历过的步数，$\min(S ......

### 题意 给出一棵 $n$ 结点树，从结点 $x$ 出发，每次从当前点的所有边中选一条走过去，$Q$ 次询问给定一个点集 $S$，随机游走直到经过 $S$ 中的每一个点至少一次的期望总步数，出发点 $x$ 默认在开始时已经被经过。 $n\le 18, Q\le 5000$ ### 解法 萌新第一 ......

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