对于树上随机游走的一类研究。

Custlo / 2023-07-19 / 原文

我们可以考虑使用高斯消元求期望，虽然 \(O(n^3)\) 但是很有一些启发性。

就是节点的期望与父亲的期望上表述有一次性。也就是说 \(f_u = a_uf_{fa} + b_u\) 这个式子。

CF1823F Random Walk

树上随机游走，求 \(s\to t\) 的路上，\(1 \to n\) 的期望经过次数。

考虑如下式子：

\[f_t = 1 \]

\[f_u = \sum_{v \in E, v \neq t} \frac{f_v}{deg_v} \]

\[f_s = 1 + \sum_{v \in E, v \neq t} \frac{f_v}{deg_v} \]

利用这些可以 \(O(n ^ 3)\) 高斯消元。

然后考虑如上结论： \(f_u = a_uf_{fa} + b_u\)，注意一些 \(t\) 的情况暂时没有考虑。

\[f_u = \frac{f_{fa}}{deg_{fa}} + \sum_{v \in S}\frac{f_v}{deg_v} + [u = s] \]

\[f_u = \frac{f_{fa}}{deg_{fa}} + \sum_{v \in S}\frac{a_vf_u + b_v}{deg_v} + [u = s] \]

\[f_u = \frac{f_{fa}}{deg_{fa}} + \sum_{v \in S}\frac{a_v}{deg_v}f_u + \sum\frac{b_v}{deg_v} + [u = s] \]

\[(1 - \sum_{v \in S}\frac{a_v}{deg_v})f_u = \frac{f_{fa}}{deg_{fa}} + \sum\frac{b_v}{deg_v} + [u = s] \]

除过去即可求得 \(a_u\) 和 \(b_u\)，为左右两项。根节点和叶子好求，于是就求出来了。除过去有些是 0！/fn

auto pre_dfs = [&] (auto &self, int u, int fa) -> void {
  for (auto &v : G[u]) {
		if (v.fi == fa) continue;
		self(self, v.fi, u);
		if (v.fi != t) v.se = qpow(G[ v.fi ].size(), mod - 2);
  }
  if (fa && fa != t) A[u] = qpow(G[fa].size(), mod - 2);
  if (u == s) {
    B[u] = 1;
  }
  else if (u == t) {
    A[u] = 0, B[u] = 1;
	for (auto &v : G[u]) {
		if (v.fi == fa) continue;
		v.se = 0;
	}
  }
};
auto dfs = [&] (auto &self, int u, int fa) -> void {
	a1[u] = 0, a2[u] = B[u];
	for (auto v : G[u]) {
		if (v.fi == fa) continue;
		self(self, v.fi, u);
		(a1[u] += 1ll * a1[ v.fi ] * v.se % mod) %= mod;
		(a2[u] += 1ll * a2[ v.fi ] * v.se % mod) %= mod;
	}
	int inv = qpow(1 - a1[u] + mod, mod - 2);
	a1[u] = 1ll * A[u] * inv % mod;
	a2[u] = 1ll * a2[u] * inv % mod;
};