opti = min ( optj + distj->i ?Vi + Si ) (1)
where j is a node on the path from town i to town 1. This relation is obtained by considering every harbinger j that may receive the message from harbinger i. By distj->i we denote the distance between nodes j and i. This distance can be computed in constant time if we initially compute a vector D, where Di is the distance from town i to the capital. A direct implementation of (1) takes O(N2) time and earns 20 points.
The special case of lines. Recurrence (1) can be rewritten as: opti = min ( optj - Dj ·Vi + Di ·Vi + Si ) (2)
When computing the value for opti, Di ·Vi + Si is constant for all j, so: opti = min ( optj - Dj ·Vi ) + Di ·Vi + Si (3)
We need to find the minimum of expressions of the form optj - Dj ·Vi. This has a useful geometric interpretation: for each node i, we consider a line in the plane given by the equation Y = opti ? Di ·X.
Finding the minimum is now equivalent to vertical ray shooting: find the lowest line in the plane intersected by the X=Vi line. To solve this query efficiently, we maintain the lower envelope of the lines. Because the road lengths are positive, we have that Dj? At each step i, we must: § query which line in the envelope produces the minimum for X=Vi § insert Y = opti ? Di·X in the envelope (possibly deleting others).
The first step can be solved efficiently using binary search, since the intersections of X=Vi with lines in the envelope are a unimodal function.
The second step can be solved in O(Δ), if Δ lines are deleted from the envelope. We simply pop the head of the stack as long as the newly inserted line completely shadows the segment at the head of the stack. Since every line in the stack is popped from the stack at most once, the overall complexity of this step is O(N). Thus, the entire algorithm runs in O(N lg N) time.
The general case. To handle arbitrary trees, we implement the dynamic program by depth-first search. To maintain the lower envelope during DFS, we have to support two data structure operations: 1. Insert a line efficiently (when moving down to a child). 2. Delete a line and restore the envelope to the previous state (when moving up to a parent).
Point 1. cannot proceed as for line graphs, since a line can be deleted multiple times. Quadratic behavior is obtained if a node has many children and the Δ is large between the node and each child. To insert a line in O(lg N) time, we can once more use binary search on a unimodal function. (Solutions that do linear insertion here earn 70 points.)
For the undo operations, we maintain the lower envelope in a global array. To delete Δ lines, we simply store the new line Δ positions back from the top of the stack, and leave the other Δ-1 positions intact. We also save the line that was overwritten by the newly inserted line. To restore the stack, we simply reset its top pointer, and restore the saved line to its original location in the stack. The overall complexity is O(N lg N).
An alternative visualization of the algorithm does not use lower envelopes, but linear programming; we maintain the convex hull, and use unimodal search to find the optimum.
Though the reasoning behind the algorithm is quite complicated, the code is fairly short (~ 40 lines).