COCI '22 Contest 4 #4 Mreža

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 5.0s
Memory limit: 512M

Problem types

The city mayor Mirko lives in a city with n neighborhoods connected with n-1 bidirectional roads such that from any neighborhood it is possible to reach every other neighborhood.

Mirko wants to upgrade some roads to reduce traffic. For every road, we know the current speed v_i vehicles drive on it, the price of upgrading c_i, and the speed of driving after upgrading s_i.

There are q unsatisfied citizens that come to visit Mirko. Each one has their suggestion for an upgrade. The suggestion of the i^\text{th} citizen is: "We should invest e_i euros in upgrading roads between neighborhoods a_i and b_i."

For each suggestion, Mirko is interested in what is the minimum driving speed between neighborhoods a_i and b_i if he spends at most e_i euros on upgrading the roads, given that his goal is to maximize the minimum driving speed between the neighborhoods a_i and b_i.

Mirko soon realized that calculating this is not an easy task and hired you to help him!

Input Specification

The first line contains the integer n (1 \le n \le 100\,000), the number of neighborhoods.

In each of the next n-1 lines there are five integers x_i, y_i, v_i, c_i, s_i (1 \le x_i, y_i \le n, 1 \le v_i < s_i \le 10^9, 1 \le c_i \le 10^9), denoting that neighborhood x_i and y_i are connected, and the current driving speed is v_i, the cost of upgrading the road is c_i, and the speed on the road after upgrading would be s_i.

The next line contains the integer q (1 \le q \le 100\,000), the number of unsatisfied citizens.

In each of the next q lines there are three integers a_i, b_i, e_i (1 \le a_i, b_i \le n, 1 \le e_i \le 10^{18}), which describe the suggestion of the i^\text{th} citizen.

Output Specification

In the i^\text{th} of the q lines, print the answer to the request of the i^\text{th} citizen.

Constraints

Subtask Points Constraints
1 21 n, q \le 1\,000
2 29 Each of the neighborhoods will be connected with at most 2 other neighborhoods.
3 60 No additional constraints.

Sample Input 1

6
1 2 5 7 10
1 3 4 8 9
3 4 7 1 15
3 5 6 3 11
3 6 5 6 8
3
2 4 15
6 4 5
3 5 10

Sample Output 1

7
5
11

Explanation for Sample 1

The illustration represents the city and its neighborhoods. On the edges are written the current driving speed, the cost of upgrading, and the speed after upgrading, respectively.

If we upgrade the roads between 1 and 2, and between 1 and 3, the driving speeds from 2 to 4 will be 10, 9, and 7 m/s. The minimum is 7 m/s.

If we upgrade the roads between 4 and 3, the driving speeds from 6 to 4 will be 5 and 15 m/s. The minimum is 5 m/s.

If we upgrade the road between 3 and 5, the driving speed from 5 to 3 will be 11 m/s.

Sample Input 2

4
1 2 5 5 8
2 3 4 6 9
3 4 6 10 7
4
1 4 16
2 4 16
1 4 10
3 4 10

Sample Output 2

6
7
5
7

Comments

There are no comments at the moment.