Marginalization, inference and sampling in MT models

Let $Q(x) \;=\; \sum_{k=1}^m \lambda_k T^k(x)$ be an MT model. We consider the basic operations of marginalization, inference and sampling, recalling that these operations have time complexity ${\cal O}(n)$ for each of the component tree distributions $T^k$.