This blog post is a submission for the Codeforces Month of Blog Posts Pt. III challenge. Thank you cadmiumky for the initiative!

Hello, Codeforces! Recently I heard a short tale about one idea on algocourses.ru (from teraqqq) and I realized the idea is powerful, so probably it should be more recognized.

This post has been written with my best knowledge. If something is incorrect, please let me know!

Intro

Dynamic Forest queries are usually solved with Link Cut Tree (LCT). However, for offline queries there's a powerful Divide&Conquer technique that avoids the heavy implementation of LCT. This blog explains this technique. Spoiler: LCT is faster.

Related techniques ($$$N$$$ denotes the number of vertices and $$$Q$$$ denotes the number of queries.):

• Auxiliary/Virtual tree

• 1️⃣ The traditional $$$Q log Q log N$$$ DCP uses DSU with rollbacks to merge vertices

• 2️⃣ The technique for $$$Q log Q$$$ DCP uses BFS on stable edges to merge vertices

Core idea:

Unlike Methods 1️⃣ and 2️⃣, we don't merge vertices. However, similar to both 1️⃣ and 2️⃣, we perform a DFS traversal on the segment tree built over the timeline. We observe that edges persisting throughout the current time segment can be compressed, provided we preserve the connectivity between vertices involved in that interval's queries.

I. Illustration of one application of this technique

We have $$$Q$$$ offline queries of the following types:

1. link $$$u$$$ $$$v$$$ ($$$1 \le$$$ $$$u$$$, $$$v$$$ $$$\le N$$$) — add an undirected edge between the vertices $$$u$$$ and $$$v$$$. The graph must remain a forest.

2. cut $$$i$$$ — remove the existing edge that was added in the $$$i$$$-th query.

3. get_path $$$u$$$ $$$v$$$ ($$$1 \le$$$ $$$u$$$, $$$v$$$ $$$\le N$$$) — output the number of edges on the simple path $$$u$$$ $$$\rightarrow$$$ $$$v$$$ or -1 if no such path exists.

Let's elaborate.

Standard D&C Setup (As in Method 2️⃣):

• Each edge is characterized by a time segment during which it exists.

• We define a recursive function solve(l, r, G) that receives time boundaries and some set of edges $$$G$$$.

• The job of the function is to answer queries occurring within $$$[l, r]$$$.

• The $$$i$$$-th query is answered in the leaf node of the segment tree (i.e., when $$$l=r=i$$$).

• The set $$$G$$$ contains sufficient information to answer all the queries in $$$[l, r]$$$.

• The sum of $$$|G|$$$ over the calls of solve is $$$O(Q log Q)$$$.

• The initial call is solve(l=0, r=Q-1, G=all_edges).

In segment tree leaves, we simply perform one BFS or DFS on $$$G$$$ to determine the length of the path $$$u \rightarrow v$$$.

Let $$$G_l$$$ be the subset of edges in $$$G$$$, whose time segment intersect with $$$[l, m]$$$.

Similarly, let $$$G_r$$$ be the subset of edges in $$$G$$$, whose time segment intersect with $$$[m+1, r]$$$.

If we didn't care about time complexity, we could simply pass $$$G$$$ to both segment tree children (i.e., call solve(l, m, G_l) and solve(m+1, r, G_r)).

Now, let's talk about the optimization that allows us to achieve the aforementioned $$$\Sigma |G| = O(QlogQ)$$$.

Unlike 2️⃣, we never merge vertices. Instead, we compress paths of edges. Consequently, every edge is also characterized by a length (initially $$$1$$$ for all the edges).

Suppose we are at some node of the segment tree corresponding to some time segment:

• We call an edge Stable if it exists during the whole time segment.

• We call a vertex Unstable if it has incident Unstable edges and/or it is an endpoint of some path(s) requested during that time segment.

Stable edges must create a forest. And Unstable edges are between Unstable vertices from different trees of this forest (and can create cycles).

Let's look at the forest created by Stable edges. It is intuitive that we care only about Auxiliary forest induced by Unstable vertices. So we can replace our Stable edges with the edges from Auxiliary forest.

So,

1. We add Unstable edges of $$$G$$$ to $$$G_l$$$ and/or $$$G_r$$$ (depending on the intersections).
2. We add Auxiliary forest of Stable edges (we merge edges) induced by Unstable vertices to BOTH $$$G_l$$$ and $$$G_r$$$.

II. Generalize this technique to other scenarios

Here are some problems this method solves (order matters):

1.P9 from Errichto's blog on SQRT decomposition (I offer a simple $$$QlogQ$$$ solution that Errichto/Radewoosh haven't mentioned here).

2.link(u,v), cut(i), compute_LCA(u,v,root).

3.342E - Xenia and Tree modification: link(u,v,weight), cut(i), make_blue(u), make_red(u), get_closest_blue(u), get_closest_red(u).

4.(Bonus, not sure about it) link(u,v,weight), cut(i), compute_sum_over_all_paths().

III. Conclusion

We can use this technique for various problems about paths on Dynamic Forest.

This technique can be coded instead of Nlog^2N HLD.

The efficiency of this technique relies on the observation that across the entire timeline, there are only $$$O(Q)$$$ «events» where the state of a vertex changes (yes, edge $$$u \rightarrow v$$$ weight/existence/etc. change means changes of $$$u$$$'s and $$$v$$$'s states).

(When we need to compute aggregate values: Tasks 3,4) The Stable vertices should have fixed states. That way, we can push values from/through the vertices that may «leave» from now on.

IV. Outro

One can practice four of these six problems in Codeforces Gym I created. My C++ solutions are in "Contest materials".

I would love to hear your opinion/ideas/suggestions on this blogpost and/or on the technique overall in the comments. Have a good day!