Programmers have already solved the trolley problem (a classical problem in philosophy). In the usual trolley problem, we have a directed graph and each edge is weighted by the number of people tied to the track (edge). The objective of the usual trolley problem is to find a path through the graph that minimizes the number of people killed by the train. But what about multitrack drifting?

Multitrack Drifting


In the trolley problem with multitrack drifting, the objective is reversed: Let's run over the largest number of people possible. Our trolley has a front carriage and a back carriage. By quickly throwing a lever after the front carriage goes over the track switch but before the back carriage goes over it, we can get the two carriages to separate onto two different tracks, maximizing the carnage. However, the trolley will be derailed unless there is a planar embedding of the graph for which the two carriages follow paths for which the corresponding vertices of the two paths are always on the same face of the planar embedding. The planar embedding must be fixed throughout the whole journey of the trolley.

Input and Output

Input: A directed, rooted, acyclic planar graph, with integer weights on the edges. The front and back carriages both begin at the root vertex. Please assume that all directed paths starting at the root and ending at a vertex with out-degree zero are of the same length. This implies that if any two directed paths start at the root or the same vertex and end at a vertex with out-degree zero or the same vertex (resp), then they have the same length (we can't 'go faster' by going one way or another, at a junction).

Output: The maximum sum of edge weights over all pairs of directed paths through the graph. Each of the two paths in the pair (the carriages) must start at the root vertex and end at a vertex with out-degree zero. If the vertices specified by the two paths are (x1,x2,x3,...) and (y1,y2,y3,...) then there must be a planar embedding of the graph such that xi and yi are always vertices of the same face of the planar embedding.

Notes: Please assume any input and output formats that can fully specify the situation (bytes, ascii, etc). Also, for clarifications: For a directed path, each edge of the directed path must match the direction of the corresponding edge of the input acyclic graph. Further, the number of edges between two vertices is at most one (it's not a 'multi-graph'), and no edge can connect a vertex to itself (no loops, as implied by acyclic property).