Yes, it's basically much faster to search, it can never get into an invalid state such as a cycle which is unresolvable.
There's a lot more details in the paper https://wiki.ros.org/Papers/TePRA2013...
Your case with two sources of odometry a ground truth and an estimate cannot be queried generically as you are now in a case where there are two resolutions for every potential leaf depending on how you traverse the graph. And if you try to fuse the two results you'll just get some weird in between state that's meaningless.
In this case you should choose which is going to be your primary and hang the alternative odometry frame off as a child not a parent. Then you can query to or from that semantically meaningful frame if you want to reference it, but all queries not specifically referencing that frame will use the same consistent tree.
Specifically for acyclic graphs, they're more expensive to search and require maintenance/checking to make sure that they stay acyclic.
I've always considered/believed the fact that KDL (now: orocos_kinematics_dynamics) doesn't/didn't support anything but tree structures to be the main reason. If the solver you're using doesn't support it, then it makes sense for the data structure to also not have support for it.
Additionally, lookups can be very efficiently implemented in trees, while arbitrary graphs can make this quite complex.
But I'm not an authoritative source here -- so just a comment.
Perhaps @tfoote knows/remembers.