Difference between revisions of "Talk:Heavy-light decomposition"
From PEGWiki
| Line 10: | Line 10: | ||
5 | 5 | ||
| − | Here a lca_improved(4,2) is returned as 4. | + | 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. |
Latest revision as of 12:39, 23 December 2013
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.
