Marginalization, inference and sampling in tree distributions

The basic operations of computing likelihoods, conditioning, marginalization, sampling and inference can be performed efficiently in tree distributions; in particular, each of these operations has time complexity ${\cal O}(n)$. This is a direct consequence of the factorized representation of tree distributions in equations (1) and (2).