## Editorial for DMOPC '21 Contest 1 P6 - Tree Jumping

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 4fecta

#### Author's Solution

Let's consider all nodes above us and the value we can get out of them. If we let be the depth of node , then to jump from node to node , it costs . Consider this a linear function for where given two parameters and , . What if we wanted to know the value at which two of these functions and intersect? Solving for :

In fact, we see that is completely irrelevant here. That is, regardless of , the intersection of any two of these functions will always have the same value. Also consider that the relative order of slopes of these functions don't change after changing the denominator by a factor of . 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 , we can get away with maintaining only one convex hull for all possible values of !*

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 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:

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

#### Alternate Solution

Let's rewrite the cost formula as , where the actual cost is the negative reciprocal of the quantity. Now, for all of our ancestors , we maintain the geometric convex hull of the points . The points are sorted in increasing 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 , note that we are looking for the minimum possible slope of a line formed by 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:

Thanks to zhouzixiang2004 for discovering this solution.