P9175 [COCI 2022/2023 #4] Mreža

### Account suspension due to “carding” in the judge.

Mayor Mirko lives in a city with $n$ neighborhoods. These $n$ neighborhoods are connected by $n - 1$ two-way roads, and from any neighborhood you can reach any other neighborhood. Mirko wants to upgrade some roads to ease traffic. For each road, we know the current driving speed $v_i$ on this road, the upgrade cost $c_i$, and the driving speed $s_i$ after upgrading. There are $q$ unhappy citizens who come to see Mirko. Each of them has their own upgrade suggestion. The $i$-th citizen suggests: “We should invest $e_i$ euros to upgrade the roads on the route between neighborhoods $a_i$ and $b_i$.” For each suggestion, Mirko is interested in the following: if his goal is to maximize the minimum driving speed between neighborhoods $a_i$ and $b_i$, then what is that minimum driving speed when he can spend at most $e_i$ euros on upgrading roads. Mirko immediately realizes that this problem is not simple, so he hires you to help him.

The first line contains an integer $n\ (2\le n\le 10^5)$, the total number of neighborhoods. The next $n - 1$ lines each contain five integers $x_i,y_i,v_i,c_i,s_i\ (1\le x_i,y_i\le n,1\le v_i

Output $q$ lines, where each line is the answer for the corresponding citizen’s suggestion.

Sample explanation $1$: The figure below shows the city and the neighborhoods. On each edge, the numbers are the current driving speed, the upgrade cost, and the driving speed after upgrading.  If we upgrade the roads between $1$ and $2$, and between $1$ and $3$, then the driving speeds from $2$ to $4$ will become $10,9,7$. The minimum is $7$. If we upgrade the road between $4$ and $3$, then the driving speeds from $6$ to $4$ will become $5,15$. The minimum is $5$. If we upgrade the road between $3$ and $5$, then the driving speed from $5$ to $3$ will become $11$. | Subtask ID | Additional Constraints | Score | | :-: | :-: | :-: | | $0$ | Sample only | $0$ | | $1$ | $n,q\le 1000$ | $19$ | | $2$ | Each neighborhood is connected to at most two other neighborhoods | $26$ | | $3$ | No additional constraints | $55$ | Translated by ChatGPT 5