First, note that the planets form a tree structure.

For 30% of the points, we can do DP and a DFS. When we are at a node, we look at all of its ancestors and choose the one where ~cost[node] \times dist(node,ancestor) + dp[ancestor]~ is minimal.

For 100% of the points:

The most important observation to make is that when we start from a node and move up toward planet ~N~, we should always buy fuel from a planet if it is cheaper than the last planet we bought fuel from. Thus, the problem now simplifies to finding the first ancestor with a fuel cost strictly less than the current planet.

We can use a segment tree to accomplish this. The indexes of the segment tree represent depth in the tree (e.g. index 1 is the top of the tree). Each node of the segment tree will keep track of the minimum fuel cost of a single planet in its range. We will use a DFS in order to generate our answers as well. When we reach a node in our DFS, we update the segment tree at the index equal to the depth of the node to the node's fuel cost.

In order to get the deepest node with a cost less than the current cost, we need to modify the query function a little bit. In the query function, check if the right side has a minimum less than the current cost. If the condition is true, go to the right child of the segment tree node. Otherwise, go to the left. If we recursively continue this process until we hit a leaf node, we will have found the deepest (rightmost) node with a cost less than our current cost.

After calling the DFS on each child node, we can update the segment tree at the correct index to infinity so that future queries cannot be affected (this update is not absolutely necessary, since you can limit the range of the modified query, but it makes the process easier).

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