Блог пользователя SlavicG

Автор SlavicG, история, 3 года назад, По-английски

Credits to FLEA for teaching me this trick.

Introduction

Recently I learnt an interesting trick I wanted to share with others. I'm not sure if this trick is well known, but I didn't know about it and didn't find any other articles on it so decided to write this blog.

Problem statement

We have a connected undirected graph with $$$n$$$ nodes and $$$m$$$ edges between them, each node having a value $$$w_i$$$ ($$$1 <= n, m <= 10^5$$$), ($$$1 <= w_i <= 10^9$$$).

Let's denote $$$f(a, b)$$$ as the minimum value of a node on a path from node $$$a$$$ to node $$$b$$$.

We have to answer $$$q$$$ queries about this graph. Each query contains $$$2$$$ nodes $$$a$$$, $$$b$$$ and asks for the maximum $$$f(a, b)$$$ over all possible paths from node $$$a$$$ to node $$$b$$$. ($$$1 <= q <= 10^5$$$).

Notes

This problem can be solved in another (more optimal) way, which is described in these comments: 1, 2. Thanks to valeriu and geniucos for mentioning it!

A similar idea from stefdasca.

Prerequisites

In order to fully understand the idea you have to know about DSU (disjoint set union) and small to large merging.

Solution

We will do some kind of DSU (disjoint set union). For each node, we don't only keep its parent, but also the queries it appears in (we store them in a map/set). Then we go through all the $$$n$$$ nodes in decreasing order of their values. When we are at a node — $$$u$$$, we "activate" it and then go through all the already activated neighbors the node has and we merge these two nodes.

How do we merge them?

First, we do the simple merge of the $$$2$$$ components with the classic $$$par[a] = b$$$. Then, we go through all queries the node is responsible for and check if it also appears in the query of the other node. If it does, we set the answer of that query to the weight of the node we are currently considering, since we know it will be the minimum on the path (because we are going through nodes in decreasing order of their values), if they don't both appear we just insert the the given query to the combined component and continue. But, since it would take too long, we merge the query sets with small to large merging (merge the node which has a smaller (in size) query set to the one that has a larger one). So, we do all this in $$$O((n + m) log^2n)$$$.

Some code

Note: ans[i] is the answer for query with index $$$i$$$.

First of all, we need the DSU functions — get (which returns the node responsible for the whole component) and union, which merges $$$2$$$ different components.

Since the only things we care about for a node are its parent and set of queries it's responsible for we can keep a pair of an integer and a map/set.

The union, as discussed in the above solution part involves small to large merging. If both nodes are responsible for a query then the answer for the query is the weight of the other node, otherwise we insert the query to the combined component.

Code for this part

After that, we need to set the initial components. Initially, nodes should have an empty query set and their parent should be themself only, and we can sort the nodes by decreasing order of their values in the same time (vector v will contain the node index on the second position). And, we can go also go through queries and add the queries responsible for a given node to a list.

Code for this part

Now for the iteration in decreasing order of the values, we keep the boolean activated for each node, which tells us whether the node was already "activated" (gone through) or not.

Code for this part

Then, we are left with outputting the answer for each query.

Variations

This trick can solve many variations of the problem, the most obvious one being that $$$f(a, b)$$$ would be the maximum value on the path instead of the minimum, which would require their little modifications

  • Проголосовать: нравится
  • +107
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Thank you sir for sharing this trick.

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

based trick

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

SlavicG top contributor poggers

»
3 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Thanks, SlavicG, with help of your blogs I can get better in cp!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +48 Проголосовать: не нравится
Why can't it be done like this?
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

You can do the same by computing a MST where the cost of an edge $$$(u, v)$$$ is given by $$$\max(val_u, val_v)$$$. Then what you're interested in is just the maximum value on a path (which can be done online in $$$\log(N)$$$ per query in several ways. I thought it's worth mentioning because this is a less known (though not difficult to prove, especially by your construction) property of MST

»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Hi there, thanks for sharing this trick. In addition to this method and the $$$w = \min (val_u, val_v)$$$ method, I would also like to mention the connections between your DSU and Reachability Tree/Kruskal Reconstruction Tree. In fact, you are building the vertex-based reachability tree in your method as you solve the queries! It is well known that the maximum value on a path from $$$u$$$ to $$$v$$$ in the reachability tree is simply $$$\text{LCA}(u, v)$$$, so we can also solve the problem not by merging the queries but by simply outputting $$$\text{LCA}(u, v)$$$ for each query after the tree is constructed. This speeds the solution up to $$$\mathcal{O}((n+q)\log n)$$$ with binary lifting, for example.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Another similar question CSAcademy Mountain Time

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

orz

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

This code is pretty weird tbh.

  1. You use map instead of set.
  2. I don't get why we need sets in the first place, during "query merging" you can just check if the query endpoints were in the different components before and will be in the same component after(yes, that means the other "clone" of this query becomes a dead weight). Doing it this way also removes a log from the complexity.
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Best trick ever!