Practice: Binary lifting
0 of 4 solved
About these problems
Apply, Connect, Reason and Stretch describe difficulty within this topic, not an official contest rating. Open any problem in any order; reading the chapter first is optional.
- 1Kth ancestorA tree is rooted at 1. For each query v k, move k parent edges upward from v. Print the reached vertex, or 0 if there are not enough ancestors. k=0 returns v.ApplyNot started
- 2Repeated successorEach vertex has exactly one outgoing successor f[v]. For each v k, apply f exactly k times and print the result. Cycles and self-loops are allowed.ConnectNot started
- 3Tree route distanceAnswer distances between pairs of vertices in an unweighted tree, measured in edges.ReasonNot started
- 4A stop along the routeFor each query a b k, follow the unique tree route from a toward b for k edges. Print that vertex, or 0 if k exceeds the route length. k=0 returns a.StretchNot started