Talk:Heavy-light decomposition

The LCA_improved algo is wrong

Consider the case

             1
            / \
           2   4
                \
                 3
                  \ 
                   5

Here a lca_improved(4,2) is returned as 4. The solution for this maybe that when the depth of both the nodes are equal, then advance the one with the heavy edge first and then the light edge otherwise (both are light) then advance any.