After making the change in the head annotation, we just need to decrease the frequencies of the old trees by one unit, and increase the ones of the new trees by one unit.
in figure 5, algorithm 1 (right) gives the pseudo-code for the algorithm, and the tree (left) shows an example of its usage.