【有后效性 DP】CF1823F Random Walk 笔记

两种思路都想到了，但是两种做法都没想出来。

做法一

模拟一下这个随机游走的过程，当他走错路的时候，他一定会走回头路，不然就不一定。

但是这个好像不好 DP，因为点和点的状态之间关联不大。

打开题解，发现可以考虑一条边的经过次数，由于每个点出发选择任意一条边的概率相同，因此一个点的所有出边经过的期望次数相同，设这个期望次数是 $f_u$，如果这条边 $u\to v$ 在 $s\to t$ 路径上，那么他一定会比走 $v\to u$ 的次数多一次，因此 $f_u\leftarrow f_v+1$，否则，进入 $v$ 的子树后一定会再从 $v\to u$ 里走出来，因此 $f_u\leftarrow f_v$，只需要两次 DFS 即可求解，最终的答案是 $f_u\times {\mathrm{deg}}_u$，时间复杂度 $O(n)$，空间复杂度 $O(n)$。

做法二

随机游走……这不是我们有后效性 DP 高斯消元求解吗？

不好孩子们是 $n\le 2\times {10}^5$……$n^3$ 被击毙了。

但是现在是在树上，所以对于 DP 方程

$$f_t=1,f_u=[u=S]+\sum _{(u,v)\in E\wedge v\ne t}\frac{f_v}{{\mathrm{deg}}_v}$$

我们可以寻找更多性质。

考虑这个转移比树形 DP 多了什么，正常的树形 DP 是 $f_v=k_v{f}_u+b_v$，即只和自己与自己的儿子有关，现在这个 DP 方程多了一个从父亲 $\mathrm{fa}$ 转移，我们考虑把他转换成正常形式。

$$\begin{array}{rl}{f}_u& =[u=S]+\sum _{(u,v)\in E\wedge v\ne t}\frac{f_v}{{\mathrm{deg}}_v}\\ f_u& =[u=S]+\frac{f_{\mathrm{fa}}}{{\mathrm{deg}}_{\mathrm{fa}}}+\sum _{v\in {\mathrm{son}}_u\wedge v\ne t}\frac{k_v{f}_u+b_v}{{\mathrm{deg}}_v}\\ f_u& =[u=S]+\frac{f_{\mathrm{fa}}}{{\mathrm{deg}}_{\mathrm{fa}}}+f_u\times \sum _{v\in {\mathrm{son}}_u\wedge v\ne t}\frac{k_v}{{\mathrm{deg}}_v}+\sum _{v\in {\mathrm{son}}_u\wedge v\ne t}\frac{b_v}{{\mathrm{deg}}_v}\\ (1-\sum _{v\in {\mathrm{son}}_u\wedge v\ne t}\frac{k_v}{{\mathrm{deg}}_v})f_u& =[u=S]+\frac{f_{\mathrm{fa}}}{{\mathrm{deg}}_{\mathrm{fa}}}+\sum _{v\in {\mathrm{son}}_u\wedge v\ne t}\frac{b_v}{{\mathrm{deg}}_v}\\ f_u& =\frac{1}{(1-\sum _{v\in {\mathrm{son}}_u\wedge v\ne t}\frac{k_v}{{\mathrm{deg}}_v})\times {\mathrm{deg}}_{\mathrm{fa}}}\times f_{\mathrm{fa}}+\frac{1}{(1-\sum _{v\in {\mathrm{son}}_u\wedge v\ne t}\frac{k_v}{{\mathrm{deg}}_v})}\times ([u=S]+\sum _{v\in {\mathrm{son}}_u\wedge v\ne t}\frac{b_v}{{\mathrm{deg}}_v})\end{array}$$

令 $k_u$ 为红色的部分，$b_u$ 为蓝色的部分，发现 $k,b$ 都是正常的树形 DP 可求，接着 $f$ 也变成正常的树形 DP 了，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。