Cached paths is usually pretty cheap for adding new nodes, but it can be quite expensive if you need to be able to move non-leaf nodes around (caveat: I've not looked at their use-cases here, I don't know if moving non-leaf nodes is an important matter) especially if the forest is deep rather than (or as well as) wide.