I have a taxonomy (tree) of product categories. To each leaf product category, I have assigned a shop department where the products of a given category can be found.
Now for each department, I would like to find the smallest number of the largest subtrees in the taxonomy.
For instance, in the example below leaf nodes have been assigned one of two departments $A$ and $B$.
The expected solution would be: $A$ has two subtrees, namely $x_2$ and $x_7$, $B$ has one subtree $x_4$.
The solution where $A$ has $x_1$ subtree is wrong because $x_1$ is the ancestor of nodes that belong to another department.
The solution where $A$ has $x_3$ and $x_7$ subtrees is wrong because we want the biggest subtrees possible.
Is it a known problem?
Is there a solution for it?