Note that the added cost of a cell depends upon which parent is chosen for it in the current leaf.

So the check for whether a cell should be added implicitly also includes the determination of what its parent cell will be.