Let \(w_0 w_1 \cdots w_k\) be the random walk. Define:

• \(p(i, v) = \mathbb{P}\left[w_i = v\right]\)
• \(dp(i, v) = \mathbb{E} \left[f(w[1\cdots i]) \mid w_i = v \right]\)
• \(dp2(i, v) = \mathbb{E} \left[f(w[1\cdots i])^2 \mid w_i = v \right]\)

Here, \(f\) counts the number of vertices \(v\) after the first \(i\) steps such that \(C_v = 0\) (indexing of \(w\) starts with \(1\) because the initial vertex \(w_0 = 1\) is not counted in the level).

Compute \(p\) for \(1 \cdots k\) using the following recurrence:

\[p(i, v) = \sum_{(u, v) \in E} \frac{p(i - 1, u)}{deg(u)} \]

Also:

\[dp(i, v) = \left[c_v = 0\right] + \frac{1}{p(i, v)}\sum_{(u, v) \in E} dp(i - 1, u) \frac{p(i - 1, u)}{deg(u)}\]

Note that above we have just calculated the weighted average of the expected values of neighbours where the weight is how much they contribute to \(p(i, v)\). Of course, if \(c_v = 0\) then the entire expression shifts ahead by \(1\).

Furthermore, if \(c_v = 1\):

\[dp2(i, v) = \frac{1}{p(i, v)} \sum_{(u, v) \in E} dp2(i-1, u) \frac{p(i - 1, u)}{deg(u)}\]

But if \(c_v = 0\):

\[dp2(i, v) = \frac{1}{p(i, v)} \sum_{(u, v) \in E} \left(dp2(i-1, u) +2 dp(i-1, u) + 1\right)\frac{p(i - 1, u)}{deg(u)}\]

This is because the addition of \(v\) increases \(f\) of the ongoing walk by \(1\), so it is analogous to saying \(E[(X + 1)^2] = E[X^2] + 2E[X] + 1\) by the linearity of expectation.

The answer is sum of \(dp2(i, v)\cdot p(i, v)\) over all \(1 \le i \le k\) where \(c_v = 1\).

Note: be careful with assigning values to impossible vertices when \(p(i, v) = 0\).

Note 2: considering \(dp'(i, v) = dp(i, v) p(i, v)\) and \(dp2'(i, v) = dp2(i, v) p(i, v)\) directly would make the equations in the formulation shorter. It represents the contribution of vertex \(v\) in the respective expected values without the conditional, i.e., the contribution of \(v\) in the expressions for \(\mathbb{E} (f(w[1..i]))\) and \(\mathbb{E}(f^2(w[1..i]))\). That’s a slightly more vague definition.

C++ code: https://atcoder.jp/contests/abc277/submissions/36447762