Merging and Unmerging Sets of Trees Efficiently
One solution

Make trees immutable, using path copying.  Give each tree a name.  Whenever you create a new tree T3 by merging two trees T1,T2, remember in T3 that it was created by merger of T1,T2 (i.e., include pointers to T1,T2 as part of the auxiliary information in the root node of T3).  Also keep track in the auxiliary information for each tree all of the original trees it was transitively created from.

Now, when you want to unmerge a tree, you can look at the auxiliary information to work out what you need to do.  When you call unmerge(T, U), look at the auxiliary information for T to find the two trees T1,T2 it was merged from; if U was used to create T1, then

unmerge(T, U) = merge(unmerge(T1, U), T2)

so you can proceed recursively.  Similarly, if U was used to create T2, then

unmerge(T, U) = merge(T1, unmerge(T2, U))

The running time of this will be proportional to the maximum "depth" of the merge operations, times the time to merge two trees.

A more efficient solution

With more sophisticated data structures, you can speed up the unmerge operation so it performs at most $O(\log n)$ merges.

Call a tree "atomic" if it wasn't created by a merge/unmerge.  The auxiliary information for each tree T will be an ordered list of the atomic trees T1,..,Tk it was created from, so that T = merge(T1,..,Tk).  This list will be stored as a persistent self-balancing binary tree with k leaves, one per atomic tree in the list, ordered in the same way they are in the list.  Each node in that self-balancing tree corresponds to an interval Ti,..,Tj of the list (namely, Ti,..,Tj are the set of leaves under that node); add metadata so that node points to the tree produced by merge(Ti,..,Tj).  Also, as auxiliary information for tree T, we'll have a map that given the name of a tree U lets you look up where in the list T1,..,Tk that U appears; this can be done with a second persistent self-balancing binary tree with k leaves, ordered by lexicographic order on the names of the atomic trees.

The merge(T1, T2) operation merges the two trees, and constructs its auxiliary information by concatenating the associated lists.  Those operations on the self-balancing binary trees can be done in $O(\log n)$ time, so this adds little overhead to the merge operation.

Finally, unmerge(T, U) can be implement as follows.  First, we look up where U appears in the associated list for T; suppose U is the ith item in the list T1,..,Tk, i.e., U = Ti.  Then we need to compute merge(T1,..,Ti-1,Ti+1,..,Tk).  It turns out that this can be done in $O(\log n)$ merges.  Why?  Well, we look at the path from Ti to the root in the self-balancing tree for T; if we take all of the siblings of the nodes on that path, and merge their associated trees in the correct order, we get merge(T1,..,Ti-1,Ti+1,..,Tk).  Since it is a self-balancing tree, its depth is at most $O(\log n)$, so there are at most $O(\log n)$ nodes along that path, so we need to do at most $O(\log n)$ merge operations.  Thus, unmerge(T, U) is about $O(\log n)$ times as slow as a merge operation.



A final note: there's nothing special here about the fact that the T1,..,Tk are trees.  They could have been any value, such as simple integers or anything else.  So, you might find it easier to think about this with simple values first.  On the other hand, this also means that my algorithm isn't taking into account the fact that the T1,..,Tk are trees; it's possible that data structures that take that into account might be able to be even more efficient.