yeetholmes619's blog

By yeetholmes619, 7 weeks ago, In English


MST, or Minimum Spanning Tree, is an acyclic subgraph of a graph, where the total weight of its edges is minimal. Their properties are often used in problems with edge-weighted graphs. But what about node-weighted graphs? A problem structured on edges can often be modified to one based on nodes. In such situations, data structures and algorithms analogous to those used for edges can be applied. Let's look at one such problem!

The Minimax problem

The minimax path problem involves finding the minimum of the maximum edge weights among all possible paths between two vertices, $$$i$$$ and $$$j$$$. And it turns out that, the minimax path always is a part of the MST!


Hence the solution involves finding the MST of the graph, and because trees only have one simple path between two vertices, either through DFS or through precomputation answering the query of $$$i$$$ $$$j$$$ in $$$O(n)$$$ or $$$O(\log(n))$$$ time.

Vertex Minimax problem

This is similar to the minimax problem, but instead of minimizing the maximum weighted edge along all paths, this deals in minimizing the maximum weighted node along all paths between two vertices. Let's see how our node analogy for MST deals this problem for us!

The Algorithm

In the original problem, we constructed a tree that had filtered out all the non-optimal paths between every pair of vertices leaving only the ones we want. Let's try to recreate the same! In our case "optimal" path would be one whose heaviest node is minimized.

Multiple paths between two vertices arise in the presence of cycles. So making a tree from a graph comes down to choosing which edge to cut in each cycle, hence let's observe a cycle in detail.

The Strategy

In a cycle, there are two simple paths between each pair of vertices and out of the two, the one with the heavier maximum weighted node, will always pass through the heaviest node in the cycle. Hence, we must cut any one of the two edges connected to the heaviest node in each cycle!


1851G - Vlad and the Mountains

I would urge you to try to solve it assuming the queries are online and relate to what we have learnt.

Initial Observations

Here is my submission link for reference : 217042760


The editorial's solution involves offline queries, do check that out too!


I don't know if this was common knowledge and couldn't find anything like it in my limited search on the net, but seemed like an interesting find :)

Please let me know if there are other problems that can be solved using this, I will link them in the blog!

UPD — 1

vgtcross mentions an elegant alternative approach in the following comment. This also aids in the understanding of the algorithm for vertex MST as the rules of adding an edge when seen through the lens of this approach makes the algorithm identical to the kruskal's algorithm for MST!

Full text and comments »

  • Vote: I like it
  • +33
  • Vote: I do not like it