【题解】CF1823F Random Walk

Statement

给定一棵 $n$ 个节点的树，求从节点 $S$ 到 $T$ 过程中经过每个点次数的期望值，答案对 $998244353$ 取值， $n \le 10^6$ 。

Solution

定义 $f_i$ 表示经过点 $i$ 的期望次数，根据随机游走的套路，我们可以得出如下关系：

$f_i = \begin{cases} \sum\limits_{\substack{(i, j) \in E, j \neq T}} \frac{f_j}{\deg_j} + [i = S] , & i \neq T \\[10pt] 1, & i = T \end{cases}$

很好解释的状态转移，一旦走到 $T$ 就结束，因此 $f_T = 1$ ，剩余的过程中由于 $S$ 为起点，初始就有一次。

显然这是一个环型 dp 问题，直接暴力高斯消元求解是 $\mathcal{O}(n^3)$ 的，我们应当从树上找到一些性质。不难发现 $f_i$ 是由 $f_{fa_i}$ 和 $f_{j, j \in son_i}$ 转移而来的，而 $fa_i$ 唯一，因此我们钦定：

$f_i \gets A_i \times f_{fa_i} + B_i$

将前面的式子转化后得到：

$\begin{aligned} f_i &= \frac{1}{\deg_{fa_i}}f_{fa_i} + [i = s] + \sum_{j \in son_i} \frac{1}{\deg_j} (A_j \times f_i + B_j) \\ \left (1 - \sum_{j \in son_i} \frac{1}{\deg_j}A_j \right) f_i &= \sum_{j \in son_i} \frac{1}{\deg_j}B_j + [i = s]+ \frac{1}{\deg_{fa_i}} f_{fa_i} \end{aligned}$

显然 $A_i, B_i$ 可以推出来：

$A_i = \frac{1}{\deg_{fa_i}} \times \frac{1}{\left ( 1 - \sum\limits_{j \in son_i} \frac{1}{\deg_j} A_j \right)} \\ B_i = \left( \sum\limits_{j \in son_i} \frac{1}{\deg_j}B_j + [i = s] \right) \times \frac{1}{\left ( 1 - \sum\limits_{j \in son_i} \frac{1}{\deg_j} A_j \right)} \\$

由此看出 $A_i$ 依赖 $A_{j, j \in son_i}$ ， $B_i$ 依赖 $B_{j, j \in son_i}$ 和 $A_{j, j \in son_i}$ ，考虑先自下而上 dfs 一遍整棵树，求出 $A$ 和 $B$ 数组，接着再 dfs 一次，从上往下求出所有的 $f_i$ 值。