This is not to be confused with DSU on Tree (Sack).
What can a Reachability Tree do?
Suppose you are given a weighted (connected) undirected graph of $$$N$$$ vertices and $$$M$$$ edges. Let's define an ordering of the edges, for example, the edges are ordered in the ascending/descending order of their weights. The reachability tree can help you with:
- Find the minimal/maximal weight of the edges when traversing from vertex $$$u$$$ to vertex $$$v$$$.
- Find the set of vertices that are reachable from a given vertex using the first $$$x$$$ edges, for some arbitrary $$$x$$$. You can store some information in this set of reachable vertices, such as the maximum value or the sum of values of all the reachable vertices.
Constructing a Reachability Tree
The reachability tree is a rooted tree that consists of $$$N + M$$$ nodes. The tree will have $$$N$$$ leaves which represent the original vertices of the graph, and the rest of $$$M$$$ internal nodes represent the edges of the original graph.
To build this tree, we start with the $$$N$$$ leaves, then iterate the edges of the graph one by one starting from the smallest one to the largest one. When adding an edge that connects $$$u$$$ and $$$v$$$, add a new node to the tree, then attach the current root(s) of $$$u$$$ and $$$v$$$ in the trees as the children of the newly added node. Finding these roots can be done using DSU data structure.
You can think of the reachability tree as a DSU but with no path compression, so each subtree of some internal node in the reachability tree is the set of vertices in the connected component that contains the associated edge at the point when you were adding it.
When possible, you may omit the edges that connect two vertices from the same connected component, and the reachability tree you end up with will only have $$$2N - 1$$$ nodes.
Example code
Solving example problems
CF1416D – Graph and Queries
Given an undirected graph with $$$N$$$ vertices and $$$M$$$ edges. Each vertex has a value written on it. You have to process two types of queries:
- Given a vertex $$$v$$$, among all vertices currently reachable from $$$v$$$, find the vertex with the largest value, output it, then replace its value with $$$0$$$.
- Delete a given edge $$$e$$$.
APIO 2020 – Swapping Cities
Given an undirected weighted graph of $$$N$$$ vertices and $$$M$$$ edges. Given $$$Q$$$ queries, in each query, suppose there are two people at vertices $$$X$$$ and $$$Y$$$. These two people want to switch places ($$$X$$$ moves to $$$Y$$$, and $$$Y$$$ moves to $$$X$$$), but they must not meet each other at any point of time when traversing the graph. The cost of a switch is the maximum weight traversed by both people. Compute the minimum cost, or tell that they can't switch places without meeting each other. Queries have to be processed online.
IOI 2018 – Werewolf
Given an undirected graph with $$$N$$$ vertices and $$$M$$$ edges. Vertices are numbered from $$$0$$$ through $$$N - 1$$$. You are given $$$Q$$$ queries, each represented as four integers $$$S$$$, $$$E$$$, $$$L$$$, $$$R$$$ ($$$L \le S$$$ and $$$E \le R$$$). You want to know whether it is possible to travel from $$$S$$$ to $$$E$$$ satisfying: suppose you visit the vertices $$$V_0, V_1, \dots, V_p$$$ in this order, there exists $$$q$$$ such that $$$L \le V_0, V_1, \dots, V_q$$$ and $$$V_q, V_{q + 1}, \dots, V_p \le R$$$.
More example problems
Thank you to the people who provided me with these example problems, here are what I have so far:
- Codechef CHEFCOMP – Chefina and Strange Tree
- Codechef TULIPS – Tiptoe through the tulips
- AtCoder CODE FESTIVAL 2017 Tournament Round 3 – Black Cats Deployment
- USACO 2014 January Contest Gold – Ski Course Rating
If you have more example problems or any suggestions, please let us know.
I solved this USACO problem by basically using this idea. It's not too hard and worth a look.
Thanks, knowledge of this tree might help with that problem
Added to the list!
Thank you for a great tutorial!
Excuse me for being grumpy, but is "Reachability Tree" just a glorified term for that beautiful solution to IOI 2018 Werewolf (and similar problems), or is it a technique that can be made much harder?
I think I'm not convinced of it's importance, because many example problems can be solved with easier techniques, or just too similar to that IOI 2018 problem.
I think this concept is also called the Kruskal Reconstruction Tree
(sorry for commenting so long after the blog was created. I just want to hopefully increase the likelihood that anyone searching for KRT will come across this blog)
.
In the second question's solution, After I find the LCA of X and Y, why do I have to find the closest switchable ancestor ?
Finding if the LCA has any node in its subtree, which is switchable, then we should use one of the transitive-child of the subtree of the LCA ( because the cost would be less ) . If there is no child in the given LCA's subtree, then we can find the closest ancestor which is switchable. Does that make sense ?
Am I wrong in my logic, please help me out. prabowo
Also one more doubt, you mentioned about using Parallel Binary search for offline. But would. the parallel binary search alone be enough ? Or we would need Persistent disjoint sets like structure keep track of which of the edges to move on left or right.
Sorry for asking so many questions from old tutorial now :( .