A Gomory-Hu week

TopCoder SRM 823 was the only round of this week (problems, results, top 5 on the left, analysis, TCO race standings). neal_wu and ksun48 were leading after the coding phase, but it all went downhill for them during the challenges. First, ksun48, who was less than 50 points away from the first place, made a quick challenge and earned -25, making neal_wu clear first with more than 50-point gap. A couple of minutes later, Kevin earned another -25. Then Neal decided to take the matters into his own hands and got a -25 of his own, which meant that while Kevin was still more than one successful challenge away, SSRS_ now needed just one +50 to take the first place and the 5 TCO race points, which he duly did closer to the end of the challenge phase. Congratulations on the victory! Neal and Kevin made two more unsuccessful challenges each, ending the round with quite bizarre -75 and -100 challenge points respectively.

In my previous summary, I have described a solution to a Codeforces problem. I'm not going to paste it here since it's very long, so please read the previous summary for context :) As the first step of my solution, I'm constructing another tree where the longest path queries become LCA queries, and then construct an inorder traversal of the new tree to answer LCA queries via RMQ queries.

tourist has pointed out this awesome comment to me, which shows that I did not really have a full understanding of what's going on when writing my solution. Indeed, let us look at the construction process of the new tree more closely and forget about future LCA queries for a second, just trying to keep the property that in the new tree the largest edge weight between any two vertices is the same as in the old tree. Then we can see that whenever we attach two subtrees to a newly created node, we don't really have to use the roots of the subtrees for that, and can use any node instead (because all edges within the subtrees have smaller weight than the currently processed edge, it does not matter which within-subtree edges will end up being used for the paths between the subtrees). And this allows us to keep all subtrees as chains, and connect them to form bigger chains, ultimately creating one big chain.

So it turns out that for any tree, we can construct a chain on the same vertices such that the maximum edge weight on the path between any two vertices is the same in the tree and in the chain, and of course the latter can be found using range-maximum queries. This chain is more or less equivalent to the inorder traversal of the auxiliary tree that was built in my solution, but I think constructing it explicitly is more beautiful and demonstrates a better understanding of the mechanics of the problem.

In an attempt to demonstrate an even better understanding of the mechanics, it seems to me that this construction is somewhat related to the Gomory-Hu construction. In fact, this construction seems to suggest that the Gomory-Hu tree can always be replaced by an equivalent Gomory-Hu chain! However, there seems to be no mention of a "Gomory-Hu chain" on the Internet, so I'm probably missing something here?

Update: Maxim Babenko has clarified the matters here: in the Gomory-Hu tree, for any pair of vertices not just the size of the minimum cut between them is equal to the size of the minimum cut in the original graph (as Wikipedia claims), but also the minimum cut itself (as a partition of the vertex set into two). In a Gomory-Hu chain the size of the cut is indeed still the same, but not the cut itself.

Thanks for reading, and check back next week!