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

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

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

Following is a simplified version of reachability tree 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:

  1. 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$$$.
  2. Delete a given edge $$$e$$$.
Solution

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.

Solution

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$$$.

Solution

More example problems

Thank you to the people who provided me with these example problems, here are what I have so far:

If you have more example problems or any suggestions, please let us know.

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

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

I solved this USACO problem by basically using this idea. It's not too hard and worth a look.

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

    Thanks, knowledge of this tree might help with that problem

    Added to the list!

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

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.

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

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)

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

.

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

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

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

    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 :( .