两种思路都想到了，但是两种做法都没想出来。
做法一
模拟一下这个随机游走的过程，当他走错路的时候，他一定会走回头路，不然就不一定。
但是这个好像不好 DP，因为点和点的状态之间关联不大。
打开题解，发现可以考虑一条边的经过次数，由于每个点出发选择任意一条边的概率相同，因此一个点的所有出边经过的期望次数相同，设这个期望次数是 \(f_u\)，如果这条边 \(u\to v\) 在 \(s\to t\) 路径上，那么他一定会比走 \(v\to u\) 的次数多一次，因此 \(f_{u}\gets f_v+1\)，否则，进入 \(v\) 的子树后一定会再从 \(v\to u\) 里走出来，因此 \(f_u\gets f_v\)，只需要两次 DFS 即可求解，最终的答案是 \(f_u\times \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\neq t}\frac{f_v}{\deg_v}
\]
我们可以寻找更多性质。
考虑这个转移比树形 DP 多了什么，正常的树形 DP 是 \(f_v=k_v f_u+b_v\)，即只和自己与自己的儿子有关，现在这个 DP 方程多了一个从父亲 \(\mathrm{fa}\) 转移，我们考虑把他转换成正常形式。
\[\begin{align*}
f_u&=[u=S]+\sum_{(u,v)\in E\wedge v\neq t}\frac{f_v}{\deg_v}\\
f_u&=[u=S]+\frac{f_\mathrm{fa}}{\deg_\mathrm{fa}}+\sum_{v\in \mathrm{son}_u\wedge v\neq t}\frac{k_vf_u+b_v}{\deg_v}\\
f_u&=[u=S]+\frac{f_\mathrm{fa}}{\deg_\mathrm{fa}}+f_u\times \sum_{v\in \mathrm{son}_u\wedge v\neq t}\frac{k_v}{\deg_v}+\sum_{v\in \mathrm{son}_u\wedge v\neq t}\frac{b_v}{\deg_v}\\
(1-\sum_{v\in \mathrm{son}_u\wedge v\neq t}\frac{k_v}{\deg_v})f_u&=[u=S]+\frac{f_\mathrm{fa}}{\deg_\mathrm{fa}}+\sum_{v\in \mathrm{son}_u\wedge v\neq t}\frac{b_v}{\deg_v}\\
f_u&={\color{Red}\frac{1}{(1-\sum_{v\in \mathrm{son}_u\wedge v\neq t}\frac{k_v}{\deg_v})\times \deg_{\mathrm{fa}}}}\times f_{\mathrm{fa}}+{\color{Blue}[u=S]+\sum_{v\in \mathrm{son}_u\wedge v\neq t}\frac{b_v}{\deg_v}}
\end{align*}
\]
令 \(k_u\) 为红色的部分，\(b_u\) 为蓝色的部分，发现 \(k,b\) 都是正常的树形 DP 可求，接着 \(f\) 也变成正常的树形 DP 了，时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n)\)。