Parallel binary search.

We are going to use parallel binary search.

For each query, we need to check if we can make all edges on the path $$$ \gt = x$$$ within given budget or not. We can classify edges in the path into three types

1) The current speed $$$v$$$ $$$ \gt =$$$ $$$x$$$

2) $$$v \lt x$$$ but upgraded speed $$$s$$$ $$$ \gt =$$$ $$$x$$$

3) The upgraded speed $$$s$$$ $$$ \lt $$$ $$$x$$$

We can see that we do not have to consider edge of type 1) and the budget required is just summation of type 2 edges in the path. For edge of type 3, we just need to check their existences in the path.

All the operations are supported by HLD or euler tour tree. (We only need to find sum in the path.)

So for each phase of parallel binary search, we can sort the event by the initial speed and upgraded speed. Maintain the sum of only type 2 edges and existence of type 3 edges on the path.

The time complexity is $$$O((n+q)log(n)log(MAX))$$$

You can check my code for more details. Code