Difference between revisions of "Talk:Heavy-light decomposition"
From PEGWiki
(Created page with "The LCA algo is wrong Consider the case 1 / \ 2 4 \ 3 \ 5 H...") |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | The | + | The LCA_improved algo is wrong |
Consider the case | Consider the case | ||
| Line 10: | Line 10: | ||
5 | 5 | ||
| − | Here a | + | 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.
