LCA - Lowest Common Ancestor

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/problems/LCASQ/
code github.com/Errichto/youtube/b...
Two homework problems:
1) Answer queries "find distance between two given nodes U and V" cses.fi/problemset/task/1135
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/Errichto/youtube/w...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.

[@Errichto]

Here are two homework problems for you:
1) Answer queries "find distance between two given nodes U and V" cses.fi/problemset/task/1135
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).

[@pycz]

Oh, I tried to solve 1-st problem with python3, looks like I get it right, but on big input I stucked with TIME LIMIT EXCEEDED. But in Statistics sections I saw an accepted python solution. Any tips to speed up python code to fit into 1 second timeout?
I am already:
1) Used collections.deque for dfs
2) Used array.array for up (partially), parents and depth arrays.
3) sys.stdin.readline() instead of input()
I will appreciate any help!

[@prakash_77]

​@@pycz I did with C++. 2 or 3 were getting TLE. It's probably because i/o is slow. I added these three at start of main function.
1.) ios::sync_with_stdio(0);
2.) cin.tie(0);
3.) cout.tie(0);
in C++ and got AC. There'll be something similar to that in Python also.

[@lakshyamittal3098]

Is the second question a little bit like Sparse Table (RMQ)? But complexity for each query will be O(Log(N)) only because we still need to find the LCA. Am I right?

[@exe2543]

@@pycz I got TLE with Java as well on the big inputs, but when I ran it locally I got the correct result. I tried using an iterative rather than recursive DFS but it still TLE's. I'm just going to assume it's an issue with reading the inputs because I have implemented the actual algorithm itself correctly and it produces the correct result (I'm using BufferedReader and PrintWriter).

[@allwell8570]

Generally, it is difficult to learn from extra-ordinary people like you. But you are exception to that also. Thank you so much.

[@mukulkumar2316]

After watching numerous errichto videos , whenever I explain my code to anyone else I get errichto's accent.
Your videos are awesome.

[@coefficient1359]

Errichto should be in the UN protected list ❤.

[@teddq7210]

😀❤️💯

[@ksg7882]

I am simple man , i see Errichto is teaching something i will click it

[@ShubhamKumar-me7xy]

It's a great initiative by you to teach algorithms. Looking forward for more such great videos. Also add some more practice problems of whatever you explain.

[@bethsuni4011]

Thanks for the lectures. I like this format a lot: short videos with explanation, code, and example.

[@hydroUNI]

YES! A THOUSAND TIMES YES! Thank you soooooo much for making a video on LCA!

[@saiprasadduduka2155]

Some of your videos(like this one) are so well made. Thnx🔥

[@saitejaballa6759]

The way you explained the binary lifting is just awesome ❤❤

[@glaucoa.9214]

Errichto one of the best, I love his videos.

[@alexandruhritcan9727]

I know how to do LCA with RMQ, but this solution is something else
I love it to bits 💚💚

[@patrykwronski8476]

Thank you Kamil for such a great explanation, keep up the good work:)

[@simone8504]

Thank you i was searching for this after the binary lifting video 👍

[@abdullahzaghmout5615]

Thank you for these videos. Keep on making them

[@RajatSingh-dg8ov]

I know that these problems are very easy for you but trust me these are very hard for me.
And if you are making it, I will watch it!. You are literal GOD in coding!.
Please keep on making these very basic videos on concepts, I really liked your Binary Search video as well!.
Thanks

[@desyfer1709]

This guy doing a god's work...whoever is the god of cp

[@GGxEpsilon]

Tourist

[@nguyentrongvanviet]

thank you so much I can finally solve the question on cses
hope more video like this from you

[@josephwong2832]

awesome explanation of LCA and Binary Lifting

[@BelalMoawadOfficial]

your explanation is great, thank u

[@sunnyrawat931]

Clear and concise. I love it.

[@itz_me_imraan02]

His voice and explanation both are soothing🙂

[@shivanshsrivastava9264]

Loved the explanation. Thanks a lot

[@iPaperPlane]

Can't believe this still *F R E E*

[@teddq7210]

Your contents are awesome ❤️

[@ani68]

This was the video which I wanted....thanks😊😊

[@ani68]

I think these concepts are very easy for kamil....😅

[@luizeduardoreis7657]

You are an amazing teacher

[@gitanshgarg3146]

Great content 🙌💯

[@dtrade4787]

Thanks man. Astounded by your brain

[@prasenjitmondal673]

Very Nice explanation. Thanks. Can you do a tutorial on heavy-light decomposition?

[@srishtikdutta8946]

Please do some tutorials on centroid and heavy light decomposition.

[@satyampal7235]

Thanks it was helpful.

[@AniketSingh-mt6zr]

Absolute beauty

[@prathamkumar2968]

The preprocessing of vector

[@pankaj2077]

He meant every query is answered in O(logN)

[@mizel_1121]

I love you bro u help me a lot

[@Harpreetsingh-qc8sf]

I am a beginner sir but really like your way hope i get green soon on cf

[@Errichto]

Good luck!

[@wow4669]

Thanks you😊

[@GGxEpsilon]

2 videos in a week. 🎉

[@GauravKumar-ue7nz]

Thank you so Much

[@Kyanqy_Tarb3r]

which compiler are you using in this video?

[@vigneshs8738]

The j iterator should only go reverse order from Log -1 to 0 and not the other which works in binary lifting?

[@seaorz]

Thanks!

[@manojmaurya9683]

People have their own kind hero.I have you #the best❤️

[@Errichto]

Thanks :)

[@mzmzgreen]

What about time/space complexity of this algorithm? Is it logN like in a binary search? I guess worst case is O(N) when first node is a root and second node is the deepest leaf, right?

[@Errichto]

We only have for-loops of size log(N) so it's O(log(N)) per query.
Preprocessing takes O(N*log(N)) space & time.

[@ramsankar585]

can we move from lowest power to highest power? If not why?

[@sumitrohilla1494]

Which drawing software is that...plz someone tell me

[@vatsalagarwal2466]

I have noticed one thing whicle actually coding for the problem. In the second loop, from LOG - 1 to 0, if we change this to 0 to LOG - 1, the program gives WA for soms tcs. Can someone explain why ? if the LCA is xth ancestor of a and b (after equalizing the depths), does it matter how we access the bits of x. It can be either fromt MSB or LSB. Please clear this concept.

[@allwell8570]

0 to LOG-1 in last for loop will not work. Because we are moving both nodes one by one to the level just below the lowest common ancestor.
Let us call this level as 'Limiting level'.
Suppose, we have to make 2 jumps to reach limiting level.
As you start for loop from 0, you'll check for 2^0 jumps from initial position, then it is allowed (as they will not be equal) , therefore you will make jump. From that position, you can check for 2, 4 ,8... jumps. But we are just 1 jump away from limiting level.
Therefore we can not reach limiting level here, that is why it is not working.

[@anonymoussloth6687]

In the case of finding lca just once, doesn't this perform worse than the linear solution? Not only does it take extra space, but we do a linear DFS to pre process all parents and then find the lca

[@notwatermango]

for small cases maybe, for larger ones the linear is worse

[@kongzilla2897]

Nice :)

[@ananyapamde4514]

May god bless you

[@pavankumar-cy6mg]

what if last for loop goes form 0 to n-1

[@miku6701]

I'm tellin y'all, this guy is friends with Megamind

[@rredy]

You used to live in Suwałki?

[@raven9965]

im guessing your using a PC, can you share what you are using to
sketch, hardware and program?

[@Errichto]

github.com/Errichto/youtube/wiki/FAQ#hardware

[@Harpreetsingh-qc8sf]

I am not able to get ideas quickly for simple adhoc problems of A B problems please suggest me some idea where to practicr for these ques.

[@Errichto]

Codeforces (div2&3, edu), Atcoder (ABC), Leetcode and basically all the platforms.

[@Harpreetsingh-qc8sf]

Thanks Errichto hope you win codejam this tym

[@juan-tj1xf]

Geeeeezz...

[@fruith_]

Likes

[@rugrid146]

COME TO BRAZIL !!!

[@josealejandrovaroncarreno1692]

is beutiful

[@hkt9100]

hackercup T-shirt lol

[@amiproject]

T

[@harryguanous7198]

Please heart me, i somehow arrived early