Given a tree topology and an assignment of character states to its leaves, the Small Parsimony Problem (SPP) consists in assigning character states to the internal nodes in a way maximizing a certain parsimony or probabilistic criterion. In the genome rearrangement field, tree leaves are permutations of gene sets, and the problem is to infer permutations at internal nodes minimizing a rearrangement distance. Almost all genome rearrangement models lead to intractable problems for the SPP. Considering only the numerical profiles on a phylogeny, the Count package (Csűrös, 2010) can be used to predict the size of gene families on internal nodes under a parsimony or probabilistic model. Here, we present a tractable version of the SPP: given a tree topology leaf-labeled by unordered gene sets, infer gene sets at internal nodes in a way minimizing the number of gain and loss episodes on the edges of the tree, while having a single gain point for each gene (i.e. under Dollo’s law). We show that the entire solution space is covered by testing four possible cases on each internal node’s content, leading to a linear-time dynamic programming algorithm for obtaining an optimal solution. We apply our InOutParsimony software to clusters of orthologous mitochondrial protein-coding genes (MitoCOGs) in both the mitochondrial and nuclear genomes of 11 land plant species. The results are discussed considering the Endosymbiotic Gene Transfer events shaping the mitochondria and nucleus contents and compared with Count’s returned numerical profiles.