It is always optimal to repair the roads which have the smallest speed. We can solve the first subtask just with this observation. For every query with using dfs we can find all the edges on the required path. Now we just update the slowest edge until we run out of money. Time complexity ~\mathcal O(nq \log n)~.

Let us assume that we want to have the minimal driving speed ~x~ on some path. If we want to traverse through some edge ~i~, there are three possible outcomes:

• ~x \le v_i~: in this case, the road speed is fast enough, we do not need to pay for a road upgrade.
• ~v_i < x \le s_i~: in this case, we need to upgrade the road to pass through it.
• ~s_i < x~: in this case, we cannot pass through this road at all. We will say that the price to pass through this edge is infinite.

Every edge has three possible 'states'. If ~x~ is smaller than or equal to its speed, we do not pay for it. If it is between ~v_i~ and ~s_i~, we need to pay for it. If it is larger than ~s_i~ we need to pay for it 'infinite' amount of coins. Therefore, in two moments the state of the edge will change: when ~x = v_i+1~ and when ~x = s_i+1~. We will call these moments 'events'. Let us gather events of all edges and sort them.

From this moment, two different solutions to this problem are possible. We can use parallel binary search to solve all queries at the same time. Every time we would go through all events and update them in a segment tree, and at certain moments return the sum of values on the path of some query. The second solution is to use a persistent segment tree. We would then for every query binary search the solution individually. In both solutions, the final time complexity is ~\mathcal O(n \log^2 n)~.