Can someone tell me if this works? It seems to be easier to implement and also creates slightly less paths (though still O(log N) ).
The problem: given any tree of size N, find a way to split it into some disjoint paths such that from any node, you can reach the root by passing through log N paths. Heavy light decomposition: https://cp-algorithms.com/graph/hld.html
I was thinking that a small modification is that instead of choosing an edge only when a child’s subtree is of size at least half of this subtree, you just choose the largest subtree. Proof that this works is the same: when you switch paths, the size of the subtree must at least double.
Edit: just noticed that the link also mentions you can do this, so I’m wondering why heavy-light decomposition is used instead of this, because this seems easier to understand and also slightly more performant (because of less paths).
