Indian Computing Olympiad

Advanced Graph Algorithms→Islands (IOI 2008)

You are visiting a park which has N islands. From each island i, exactly one bridge was constructed. The length of that bridge is denoted by Li. The total number of bridges in the park is N. Although each bridge was built from one island to another, now every bridge can be traversed in both directions. Also, for each pair of islands, there is a unique ferry that travels back and forth between them.

Since you like walking better than riding ferries, you want to maximize the sum of the lengths of the bridges you cross, subject to the constraints below.

• You can start your visit at an island of your choice.
• You may not visit any island more than once.
• At any time you may move from your current island S to another island D that you have not visited before. You can go from S to D either by:
• Walking: Only possible if there is a bridge between the two islands. With this option the length of the bridge is added to the total distance you have walked, or
• Ferry: You can choose this option only if D is not reachable from S using any combination of bridges and/or previously used ferries. (When checking whether it is reachable or not, you consider all paths, including paths passing through islands that you have already visited.)

Note that you do not have to visit all the islands, and it may be impossible to cross all the bridges.

Constraints:

• 2 ≤ N ≤ 10⁶
• 1 ≤ Li ≤ 10⁸ (length of bridge i)

The condition on taking ferries can be explained as follows:

We start with an undirected graph (the bridges). Each ferry we take adds an edge. When we take a ferry we will add an edge — this edge can be added only if it connects two previously disconnected components. So, we cannot add a ferry edge within the same component.

The condition on how bridges were originally built promises us that when we start our walk (only bridges), each component of size K contains exactly K edges (each island in the component has one outgoing bridge and the corresponding edge stays within the component).

So, graph theoretically, the problem is the following:

Initially we have a graph with components. Each component of size K has exactly K weighted edges.

The solution is to find the longest path in each component and then string these paths together with ferry edges (remember we can start at any island and we can enter and leave a component at any island).

How do we find the longest path in a component? In general, this is hard, but we have a special case where there are K vertices and K edges.

Claim: A graph with K vertices and K edges consists of a single cycle with trees hanging off the vertices along the cycle.

Proof: We can think of the graph as being obtained by adding 1 edge to a tree with K vertices and K edges. The last edge we added creates a unique cycle.

One solution is the following:

• The longest path cannot use all edges of the cycle. If we omit an edge from the cycle, the rest of the graph is a tree. We systematically drop each edge in the cycle and compute the longest path in each tree. The best of these is the answer.

How do we find the longest path on the tree?

• Root the tree at any vertex. Run a DFS and find the furthest vertex v.
• Now root the tree at v and again do a DFS to fina the furthest vertex w from v. The path v→w is the longest path.

This algorithm takes time NC where C is the size of the cycle.

To get an O(N) solution, we work as follows.

Consider the C trees {T1,T2,...,TC} hanging off the cycle (Ti could be trivial, just the one node on the cycle).

For each tree Ti, compute

• Ni, the longest path from a leaf node to the vertex where the tree is attached to the cycle
• Mi, the longest path within the longest path

Now, pick two trees and a segment of the cycle so that the sum is maximal (enter at the first tree, walk by longest path to the cycle, traverse the segment of the cycle, exit via the second tree).

---