I realize the last few weeks have been a bit rough for Div2 viewers. The problems have been near ICPC World Finals level and I want to vary the difficulty of topics to make sure everyone can enjoy the show. This week I'll be covering a technique that is more accessible! This technique is called binary lifting. It is a technique for quickly walking up a rooted tree.
In last week's episode, I discussed the solution to the problem Ski Resort from NAIPC. The problem required us to compute LCAs (least common ancestors) quickly on rooted trees. I'll be expanding on how to do that in this episode.
You'll also learn how to quickly know the length of paths in trees, find bottle neck edges quickly in weighted graphs, and other useful tricks.
See you live! (stream, time)