CSES - New Roads Queries Solution

[Oz121]

For this problem, the solution given (https://usaco.guide/problems/cses-2101-new-roads-queries/solution) uses Platinum topics.

There's a more elementary solution with parallel binary search here: https://duoblogger.github.io/assets/pdf/memonvyftw/guide-t-cp.pdf (section 15.5.3). Also, the top user solution uses parallel binary search.

[bqi343]

another way (though not simpler) is to convert the tree into a line, then it reduces to RMQ queries which can be answered in $O(1)$ time each.

ref: https://codeforces.com/blog/entry/71568?#comment-559304

[TheGamingMousse]

we can also use dsu stuff described in the solution to this problem