Well, since we have ∀x.Φ = ¬∃x.¬Φ, we can compute the universal quantification by an existential one. Similarly, you could compute the latter by the former: ∃x.Φ = ¬∀x.¬Φ. That is why the BDD was negated before the existential quantification shall be applied.

However, you need to know an algorithm for one of the two.