dimss's blog

By dimss, history, 2 months ago, translation, In English

It seemed to me that this was nowhere to be found and I came up with something new, but after I proposed a task on codeforces, one of the coordinators said that a couple of years ago he had already seen a task where something similar was used. Therefore, the task was rejected. Since I couldn't come up with a more interesting task for this trick, I'll just write about it in a blog.


Let some problem be given that we can solve using centroid decomposition. For example, like this. Given a tree, for each vertex assigned number a[i]. There are 2 types of queries.

  1. Given $$$v$$$, $$$d$$$, $$$c$$$. You are to recolor all vertices at a distance no greater than $$$d$$$ from vertex v in color $$$c$$$.

  2. Given $$$v$$$. We need to find out the color of vertex $$$v$$$.

Now this task is not on a tree, but on a connected graph. But there is one very interesting limitation: m — n + 1 $$$\le$$$ 100. hat is, no more than 100 edges were added to the tree.

First, let me remind you how the problem was solved on the tree. We built a tree of centroids of depth $$$O(\log n)$$$, for each centroid we stored a structure that could color vertices from $$$C$$$ at a distance of no more than $$$d$$$ and recognize the color of the vertex. This structure is called a stack, which stores triplets of elements (distance, color, time). Need to mention, that the distance strictly decreases. Then, when painting, you need to remove some elements from the end of the stack and put a new element. So, when requesting a color, the answer can be found by binary search by local depth $$$v$$$.

We have learned to respond to requests if we paint vertices from a given centroid. Now let's go through all the centroids $$$C$$$, which are the ancestors of $$$v$$$ in the centroid tree, and for them we will perform the operations above. If the query is of the first type, and we paint from $$$v$$$ at a distance of no more than $$$d$$$, then from $$$C$$$ we need to paint at a distance of at most $$$d−dist(v,C)$$$ If we are now answering a query of the second type, then from all the colors we need to choose the one which has the maximum time. Why does it work? Suppose there was a paint request from $$$v$$$ that hit $$$u$$$, whose color we now want to know. Then there is a centroid $$$C=lca(v,u)$$$ in the tree of centroids. $$$C$$$ is a common centroid for both $$$v$$$ and $$$u$$$. Moreover, it is on the path from $$$v$$$ to $$$u$$$ in the source tree. Then when we iterate over $$$C$$$, we are guaranteed the correct answer.

Now, when we have not a tree, but a graph, it is impossible to build a tree of centroids. Let's rewrite the definition of centroid and build something similar. get(G) will produce a new centroid according to the following algorithm:

  1. If G has a cycle, then return any vertex on the cycle.

  2. If G is a tree, then return any ordinary centroid.

Another change in the construction is that now the depths of the vertices must be searched not with dfs, but with bfs. Then the tree of new centroids will look like a bamboo of 100 vertices, from which the tree of ordinary centroids is suspended. I claim that then the algorithm above will work correctly. Again, suppose there was a coloring in $$$v$$$ that hits $$$u$$$, and we want to know the color of $$$u$$$. Then there is a vertex $$$C$$$ that is an ancestor of $$$lca(v,u)$$$ (note that not exactly lca, but an ancestor of lca) such that the shortest path from $$$v$$$ to $$$u$$$ passes through vertex $$$C$$$ and when , the correct answer will be calculated. And when we sort it out, the correct answer will be calculated.

Processing the queries of first type amortized takes $$$O(m−n+1+\log n)$$$, and the second $$$O((m−n+1+\log n) \log n)$$$.

Other problems

All the tasks that I know and know how to solve, where centroids are used to answer queries (there are not very many of them), I know how to generalize to a graph. But, unfortunately, not every task on the tree can be generalized in this way. For example, if centroids are used to count the number of paths in the tree (more precisely, the number of pairs of $$$v$$$, $$$u$$$), then some paths will be counted several times if there are several extreme paths between them. The answer obtained in this way gives a good upper bound. The real answer is less than no more than $$$(m - n + 1)n$$$.

Thanks to andreyDagger for the English translation.

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

2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

It's so cool!

2 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Nice idea

2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Could you please describe the construction process a bit more broadly? BTW great blog!

  • »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Trying to find a cycle in the graph with dfs.
    2. If the cycle is found, we take as C any vertex from the cycle
    3. If the loop is not found, then it is a tree. We start dfs2 from any vertex and calculate the sizes of the subtrees. 3.2. Run dfs3 from the same vertex as dfs2, which will find the centroid. If all neighbors have sz[u] <= sz[v] / 2, then v is a centroid. Otherwise, we run dfs3 from the largest neighbor.
    4. Running bfs from C to search for depths.
    5. Remove C from the graph, run recursively from all connected components.
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Strongly reminds me of this problem from 300iq contest at Petrozavodsk 2020 Winter with a similar idea of generalizing the centroid decomposition for some special graph

2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm pretty sure there was a problem like this in codechef a few years ago. Cool trick though.

2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For this particular problem, you can just consider any spanning tree, find the vertices that are endpoints to the extra edges, do some bfs from all these special vertices to compute distances to each vertex, and then apply the operation and query for each rooted tree independently as well as for the unrooted spanning tree (you need centroid decomp for this part).

Complexity is $$$O(q((m-n+1) + \log n))$$$. You can even do it with $$$O(n)$$$ memory if you are allowed to process the queries offline.