Tutorial on LCA algorithm. We use Binary Lifting to get O(N*log(N)) preprocessing and O(log(N)) to find the lowest common ancestor of two nodes in a tree.
Binary Lifting video • Binary Lifting (Kth An...
SPOJ problem www.spoj.com/p...
code github.com/Err...
Two homework problems:
1) Answer queries "find distance between two given nodes U and V" cses.fi/proble...
2) Given a tree with weighted edges (i.e. every edge has some value), answer queries "given two nodes U and V, find minimum weight along path U-V". (I don't have a source for this one).
Coding live streams - / errichto
FAQ - github.com/Err...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
Негізгі бет LCA - Lowest Common Ancestor
Пікірлер: 83