Omkar and Tours
Contest: Technocup 2022 - Elimination Round 1
Difficulty rating: 3300
Tags: data structures, divide and conquer, sortings, trees

Omkar is hosting tours of his country, Omkarland! There are $$$n$$$ cities in Omkarland, and, rather curiously, there are exactly $$$n-1$$$ bidirectional roads connecting the cities to each other. It is guaranteed that you can reach any city from any other city through the road network.

Every city has an enjoyment value $$$e$$$. Each road has a capacity $$$c$$$, denoting the maximum number of vehicles that can be on it, and an associated toll $$$t$$$. However, the toll system in Omkarland has an interesting quirk: if a vehicle travels on multiple roads on a single journey, they pay only the highest toll of any single road on which they traveled. (In other words, they pay $$$\max t$$$ over all the roads on which they traveled.) If a vehicle traverses no roads, they pay $$$0$$$ toll.

Omkar has decided to host $$$q$$$ tour groups. Each tour group consists of $$$v$$$ vehicles starting at city $$$x$$$. (Keep in mind that a tour group with $$$v$$$ vehicles can travel only on roads with capacity $$$\geq v$$$.) Being the tour organizer, Omkar wants his groups to have as much fun as they possibly can, but also must reimburse his groups for the tolls that they have to pay. Thus, for each tour group, Omkar wants to know two things: first, what is the enjoyment value of the city $$$y$$$ with maximum enjoyment value that the tour group can reach from their starting city, and second, how much per vehicle will Omkar have to pay to reimburse the entire group for their trip from $$$x$$$ to $$$y$$$? (This trip from $$$x$$$ to $$$y$$$ will always be on the shortest path from $$$x$$$ to $$$y$$$.)

In the case that there are multiple reachable cities with the maximum enjoyment value, Omkar will let his tour group choose which one they want to go to. Therefore, to prepare for all possible scenarios, he wants to know the amount of money per vehicle that he needs to guarantee that he can reimburse the group regardless of which city they choose.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$), representing the number of cities and the number of groups, respectively.

The next line contains $$$n$$$ integers $$$e_1, e_2, \ldots, e_n$$$ ($$$1 \leq e_i \leq 10^9$$$), where $$$e_i$$$ represents the enjoyment value for city $$$i$$$.

The next $$$n-1$$$ lines each contain four integers $$$a$$$, $$$b$$$, $$$c$$$, and $$$t$$$ ($$$1 \leq a,b \leq n$$$, $$$1 \leq c \leq 10^9$$$, $$$1 \leq t \leq 10^9$$$), representing an road between city $$$a$$$ and city $$$b$$$ with capacity $$$c$$$ and toll $$$t$$$.

The next $$$q$$$ lines each contain two integers $$$v$$$ and $$$x$$$ ($$$1 \leq v \leq 10^9$$$, $$$1 \leq x \leq n$$$), representing the number of vehicles in the tour group and the starting city, respectively.

Output format:
Output $$$q$$$ lines. The $$$i$$$-th line should contain two integers: the highest possible enjoyment value of a city reachable by the $$$i$$$-th tour group, and the amount of money per vehicle Omkar needs to guarantee that he can reimburse the $$$i$$$-th tour group.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
A map of the first sample is shown below. For the nodes, unbolded numbers represent indices and bolded numbers represent enjoyment values. For the edges, unbolded numbers represent capacities and bolded numbers represent tolls.

For the first query, a tour group of size $$$1$$$ starting at city $$$3$$$ can reach cities $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$. Thus, the largest enjoyment value that they can reach is $$$3$$$. If the tour group chooses to go to city $$$4$$$, Omkar will have to pay $$$8$$$ per vehicle, which is the maximum.

For the second query, a tour group of size $$$9$$$ starting at city $$$5$$$ can reach only city $$$5$$$. Thus, the largest reachable enjoyment value is still $$$3$$$, and Omkar will pay $$$0$$$ per vehicle.

For the third query, a tour group of size $$$6$$$ starting at city $$$2$$$ can reach cities $$$2$$$ and $$$4$$$. The largest reachable enjoyment value is again $$$3$$$. If the tour group chooses to go to city $$$4$$$, Omkar will have to pay $$$2$$$ per vehicle, which is the maximum.

A map of the second sample is shown below:

For the first query, a tour group of size $$$5$$$ starting at city $$$1$$$ can only reach city $$$1$$$. Thus, their maximum enjoyment value is $$$1$$$ and the cost Omkar will have to pay is $$$0$$$ per vehicle.

For the second query, a tour group of size $$$4$$$ starting at city $$$1$$$ can reach cities $$$1$$$ and $$$2$$$. Thus, their maximum enjoyment value is $$$2$$$ and Omkar will pay $$$1$$$ per vehicle.

For the third query, a tour group of size $$$3$$$ starting at city $$$1$$$ can reach cities $$$1$$$, $$$2$$$, and $$$3$$$. Thus, their maximum enjoyment value is $$$3$$$ and Omkar will pay $$$1$$$ per vehicle.

For the fourth query, a tour group of size $$$2$$$ starting at city $$$1$$$ can reach cities $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$. Thus, their maximum enjoyment value is $$$4$$$ and Omkar will pay $$$1$$$ per vehicle.

For the fifth query, a tour group of size $$$1$$$ starting at city $$$1$$$ can reach cities $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$. Thus, their maximum enjoyment value is $$$5$$$ and Omkar will pay $$$1$$$ per vehicle.

Example input:
5 3
2 2 3 3 3
1 2 4 7
1 3 2 8
2 4 8 2
2 5 1 1
1 3
9 5
6 2

Example output:
3 8
3 0
3 2

Example input:
5 5
1 2 3 4 5
1 2 4 1
1 3 3 1
1 4 2 1
2 5 1 1
5 1
4 1
3 1
2 1
1 1

Example output:
1 0
2 1
3 1
4 1
5 1

Editorial:
First, note that we can process all the queries offline. We can sort the queries by the number of vehicles in the tour group and process them in decreasing order.
Now, consider solving a version of the problem with distinct enjoyment values. Then, there will always be exactly one reachable city with the maximum enjoyment value. To solve this, we can maintain a DSU that stores, for each connected component, the maximum enjoyment value and the index of the node with the maximum enjoyment value, which we denote as $$$enj[u], mxi[u]$$$ for a connected component $$$u$$$. When merging two connected components $$$u$$$, $$$v$$$, we simply take $$$enj[u] = \max(enj[u], enj[v]), mxi[u] = \text{arg}\max(mxi[u], mxi[v])$$$. Now, consider processing a query with starting node $$$a$$$ and number of vehicles $$$x$$$, we denote its "connected component" $$$u$$$ as the connected component of $$$a$$$ in the graph that contains only edges with capacity $$$\geq x$$$. Finding the maximum enjoyment value that can be reached from $$$a$$$ is simple; we can just output $$$enj[u]$$$. To compute the second value, because there is only one node with the maximum enjoyment value ($$$mxi[u]$$$), we can find the maximum edge on the path from $$$a$$$ to $$$mxi[u]$$$ using binary lifting. (Denote this as $$$\text{maxEdge}(a, mxi[u])$$$.)
We now consider the original problem, with non-distinct enjoyment values. However, here we make the key observation: for each query, the maximum toll edge always lies on either all the paths from node $$$a$$$ to any node with maximum enjoyment value, or on a path between two nodes with maximum enjoyment value. To show this, $$$\ell$$$ be the node with maximum enjoyment value whose path to $$$a$$$ contains the maximum toll edge, and let $$$m$$$ be an arbitrary node with maximum value. The path from $$$\ell$$$ to $$$a$$$ is completely contained in the union of the path from $$$m$$$ to $$$a$$$ and the path from $$$\ell$$$ to $$$m$$$. Therefore, the maximum toll edge lies on at least one of these path as desired.
Using this observation, we can modify our DSU to handle the general case. First, we now let $$$mxi[u]$$$ to be the index of any maximum enjoyment value node in $$$u$$$. We also add a new variable, $$$tol[u]$$$, which denotes the maximum toll cost among all paths between nodes of maximum enjoyment value in connected component $$$u$$$. Now, when merging components $$$u$$$ and $$$v$$$, if $$$enj[u]$$$ is not equal to $$$enj[v]$$$, then we can simply take all the above values from the component with a larger $$$enj$$$. However, if $$$enj[u] = enj[v]$$$, we will only need to update $$$tol[u]$$$. To do this, we need to consider edges that could possibly connect the two components along with ones within the components, so we let $$$tol[u] = max(tol[u], tol[v], \text{maxEdge}(mxi[u], mxi[v]))$$$. Again, maxEdge can be computed using binary lifting.
Now, to process the queries, we will make use of our observation. For a query with starting node $$$a$$$ and connected component $$$u$$$, the maximum enjoyment value is again $$$enj[u]$$$. However, the second value can now be more easily computed by $$$\max(\text{maxEdge}(a, mxi[u]), tol[u])$$$.
As the preprocessing necessary for binary lifting takes $$$O(n \log n)$$$ time, and all the queries can be answered in $$$O((n + q) \log n)$$$ time, the overall complexity is $$$O((n + q) \log n)$$$, which is fast enough.