In other words all shared leaf set sizes can be calculated in time O(n2). First the shared leaf set sizes for subtrees that to not contain an arbitrary node r and r' from each tree are calculated in time O(n2). Then the shared leaf set sizes of subtrees that do contain r or r' (or both) are calculated constant time for each shared leaf set. Since there are O(n2) shared leaf sets the total time usage is O(n2).