  We introduce the notion of quota trees in directed graphs. Given a
nonnegative integer ``quota'' for each vertex of a directed multigraph $G$, a
quota tree is an immersed rooted tree which hits each vertex of $G$ the
prescribed number of times. When the quotas are all one, the tree is actually
embedded and we recover the usual notion of a spanning arborescence (directed
spanning tree). The usual algorithms which produce spanning arborescences with
various properties typically have (sometimes more complicated) ``quota''
analogues.
  Our original motivation for studying quota trees was the problem of
characterizing the sizes of the Myhill-Nerode equivalence classes in a
connected deterministic finite-state automaton recognizing a given regular
language. We show that the obstruction to realizing a given set of M-N class
sizes is precisely the existence of a suitable quota tree.
  In this paper we develop the basic theory of quota trees. We give necessary
and sufficient conditions for the existence of a quota tree (or forest) over a
given directed graph with specified quotas, solving the M-N class size problem
as a special case. We discuss some potential applications of quota trees and
forests, and connect them to the $k$ lightest paths problem. We give two proofs
of the main theorem: one based on an algorithmic loop invariant, and one based
on direct enumeration of quota trees. For the latter, we use Lagrange inversion
to derive a formula which vastly generalizes both the matrix-tree theorem and
Cayley's formula for counting labeled trees. We give an efficient algorithm to
sample uniformly from the set of forests with given quotas, as well as a
generalization of Edmonds' algorithm for computing a minimum-weight quota
forest.
