Motivation
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!
Why?A good way to get the intuition is by thinking what if no minimax path lie on the MST? It comes back to the edges we choose in a cycle. We cut the edge with the highest weight to make the MST so among all paths that were accessible in the original graph, only the ones with the heaviest edges are inaccessible in 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!
CodeThere are several ways to implement this, one that I thought of is this:
#define vpii vector<pair<int,int>>
#define pii pair<int,int>
#define pb push_back
#define vi vector<int>
vpii vertexMST(vpii edges, vi weight){
int m = edges.size();
int n = weight.size();
//add v,u for all u,v in the list
for(int i=0;i<m;i++){
edges.pb({edges[i].second,edges[i].first});
}
//sort based on weight of first vertex
sort(edges.begin(),edges.end(),[&](pii a,pii b){
return weight[a.first] < weight[b.first];
});
vpii new_edges;
vi vis(n,0);
for(auto it:edges){
int u = it.first;
int v = it.second;
//if we haven't added vertex u to our tree/forest yet then add it
if(!vis[u])
vis[u] = 1;
//if adding vertex v doesn't create a cycle and v is in our tree/forest then add it
if(dsu.find(u) != dsu.find(v) and vis[v]){
new_edges.pb({u,v});
dsu.merge(u,v);
}
}
return new_edges;
}
I would urge you to try to solve it assuming the queries are online and relate to what we have learnt.
Initial Observations - The lowest vlad's energy can go throughout his travel is by $$$h_{max}$$$ — $$$h_{initial}$$$, where $$$h_{max}$$$ is the highest mountain in his path, and $$$h_{initial}$$$ is the height of his first mountain.
- If vlad can travel between u and v with energy e, there will always exist a simple path which he can travel along. (Think about what effect does going in a loop or repeating an edge do the energy)
SolutionFrom our initial observations, we can deduce that this problem is equivalent to finding the minimum possible $$$h_{max}$$$ in the journey from $$$u$$$ to $$$v$$$, and then checking if $$$h_{max}$$$ — $$$h_u$$$ $$$\leq$$$ $$$e$$$.
So we first create the vertex MST, then after rooting the tree at an arbitrary node, then using the technique of binary lifting we precompute ancestors in powers of 2 and also maximum weighted node in the path to that ancestor.
Hence whenever we get a query for two vertices $$$u$$$ and $$$v$$$, we can just find their LCA (Lowest common ancestor) and take the max of the maximum weighted node from each of the vertex to the LCA and that would be our $$$h_{max}$$$ for the path from $$$u$$$ to $$$v$$$!
precomputation : $$$O(n\log (n))$$$ query time : $$$O(\log (n))$$$
Here is my submission link for reference : 217042760
Note
The editorial's solution involves offline queries, do check that out too!
Conclusion
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!
