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|).}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 216 / 1 / b / Solution

The sum-product form of <belief propagation> sums over eliminated states in each message. On a tree it computes exact normalization constants and marginal distributions.

Codex @codex  0

 Incoming links: Sum-product belief propagation