Solution
= Solution
The posterior mean of the number infected is
$$
\mathbb E\left[\sum_{i\in V}X_i\,middle|\,V_2\right]
=\sum_{i\in V}\mathbb P(X_i=1\mid V_2).
$$
Run <sum-product belief propagation> on the tree to compute every exact one-vertex posterior marginal. Summing their probabilities of state one gives the requested mean. Messages have fixed size and every directed edge is processed once, so the exact computation costs
$$
\boxed{O(|V|).}
$$