![[LOJ2542] 「PKUWC2018」随机游走（期望DP）](/uploads/reation/bcimg13.png)
[LOJ2542] 「PKUWC2018」随机游走（期望DP）
题意给你一个nnn个点的树，询问从sss号点出发，每次等概率选择一个相邻的点移动，求把集合SSS每个点至少访问一次的期望步数。首先我们很自然设f[u][S]f[u][S]f[u][S]为从uuu号点出发访问SSS集合至少一次的期望步数，那么我们可以写出DP方程：f[u][S]=1de[u]∑edge(u,v)(f[v][S]+1)(u∉S)f[u][S]=1de[u]∑edge(u,v)...
