Open Oz121 opened 1 month ago
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.
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
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.