Author's Solution

Let's consider all nodes above us and the value we can get out of them. If we let ~d_i~ be the depth of node ~i~, then to jump from node ~a~ to node ~b~, it costs ~(d_b - d_a)/(r_a - c_b)~. Consider this a linear function for ~a~ where given two parameters ~x~ and ~c~, ~f_a(x, c) = (x - d_a)/(r_a - c)~. What if we wanted to know the ~y~ value at which two of these functions ~f_a~ and ~f_b~ intersect? Solving for ~y~:

$$\displaystyle y = \frac{x - d_a}{r_a - c} \Rightarrow (r_a - c)y + d_a = x$$ $$\displaystyle y = \frac{x - d_b}{r_b - c} \Rightarrow (r_b - c)y + d_b = x$$ $$\displaystyle r_a \cdot y - c \cdot y + d_a = r_b \cdot y - c \cdot y + d_b$$ $$\displaystyle (r_a - r_b)y = (d_b - d_a)$$ $$\displaystyle y = \frac{d_b - d_a}{r_a - r_b}$$

In fact, we see that ~c~ is completely irrelevant here. That is, regardless of ~c~, the intersection of any two of these functions will always have the same ~y~ value. Also consider that the relative order of slopes of these functions don't change after changing the denominator by a factor of ~c~. If we recall the algorithm to maintain a convex hull of linear functions, the only two properties we need to be consistent are the location of intersection (to pop lines from the back) and the relative slopes (so that we can sort the lines for the building process). Since these are constant across all possible ~c~, we can get away with maintaining only one convex hull for all possible values of ~c~!*

It still remains to find a way to sort the lines and the "query nodes" so that we can insert the lines into the hull in sorted order while ensuring that ~r_a > c_b~ holds. For this, we may use something akin to CDQ divide-and-conquer with centroid decomposition. At each step, we update the answer for all nodes below and including the centroid using the functions given by all the ancestors of the centroid. Then, we may remove this centroid and recurse on all of the new components that are formed. This allows us to collect all the functions and queries to sort them, which leads to a sufficiently fast solution.

Time Complexity: ~\mathcal{O}(N \log^2 N)~

*Actually, we've only proven that the ~y~ coordinates of the intersection points are constant, which means that the lower left hull of points over ~y~ is maintainable. However, since the slopes of all the lines are always positive, this transfers maintainability to the lower right hull over ~x~, which is the property that we actually need since the queries are over fixed ~x~ and not ~y~.

Alternate Solution

Let's rewrite the cost formula as ~(c_b - r_a)/(d_b - d_a)~, where the actual cost is the negative reciprocal of the quantity. Now, for all of our ancestors ~a~, we maintain the geometric convex hull of the points ~(d_a, r_a)~. The points are sorted in increasing ~x~ as we run a DFS through the tree, so every time we add a point the new hull is a prefix of the old hull with the new point at the end. We can binary search for the location the new point is and undo this added point after by copying back what the previous element at that position was (since only one position gets changed in each update). To find the answer for node ~b~, note that we are looking for the minimum possible slope of a line formed by ~(d_b, c_b)~ and a potential ancestor point. It is not hard to prove that the optimal point is tangent to the convex hull of ancestor points, so we can compute the answer using ternary search.

Time Complexity: ~\mathcal{O}(N \log N)~

Thanks to zhouzixiang2004 for discovering this solution.