ifsmirnov's blog

By ifsmirnov, history, 2 years ago, In English,

TL;DR: is it possible to construct an Euler tour tree which supports LCA, subtree sum and rerooting?

Euler tour tree (ETT) is a method for representing a rooted undirected tree as a number sequence. There are several common ways to build this representation. Usually only the first is called the Euler tour; however, I don't know any specific names for others and will call them Euler tours too. All of them have some pros and cons. I want to discuss if we can build an algorithm which contains benefits from each one. Maybe this post also could be a tutorial for beginners. The first way is to write down all edges of the tree, directed, in order of DFS. This is how ETT is defined on, for example, Wikipedia.

     1
    / \
   2   5
  / \
 3   4

[1-2] [2-3] [3-2] [2-4] [4-2] [2-1] [1-5] [5-1]

The second way is to store vertices. Each vertex is added to the array twice: when we descend into it and when we leave it. Each leaf (except maybe root) has two consecutive entries.

     1
    / \
   2   5
  / \
 3   4

1 2 3 3 4 4 2 5 5 1

The third way implies storing vertices too, but now each vertex is added every time when we visit it (when descending from parent and when returning from child).

     1
    / \
   2   5
  / \
 3   4

1 2 3 2 4 2 1 5 1

Further all ETT's are stored in a Cartesian tree (treap) unless other explicitly stated. first(v) and last(v) are positions of first and last occurrence of vertex v in the array (in 2nd and 3rd cases).

So, how these representation can be used?

First, you should notice that a subtree is always mapped to a segment. Thus you can solve subtree queries via segment queries. E.g. if you want to add values to nodes and find subtree sum, you just make a BIT on a 2nd type tour. add(v, x) becomes add(first(v), x) in BIT, and get_sum(v) becomes get_sum(first(v), last(v)) in BIT. There is also a trick to compute sum on path: add(v, x) becomes add(first(v), x), add(last(v),  - x) in BIT, and get_sum_on_path_from_root(v) is get_sum(0, first(v)) (you can check that it works using pencil and paper).

You can also use ETT for finding LCA. Use the 3rd type. Make an additional array h, where h[i] = height(v[i]). Then lca(u, v) = v[argmin(first(u), first(v)) in h]. Why? Because LCA(u, v) is a highest vertex which is between u and v in DFS traverse order. Sometimes I prefer this method to binary accent (not sure if translated correctly) because it proved to be faster and consumes linear memory.

The fact that a subtree is maps to a segment gives us some more benefits. With the first and third approach you can reroot the tree simply rotating the array. You may avoid some pain in the neck with the third approach if you do not store last number for the root (thus vertex v will have exactly deg(v) occurrences). You also can perform link-cut operations simply cutting the segment from the array. It is done quite straightforward when you store edges, and with vertices you should carefully deal with duplicating of the subtree's former ancestor.

However, although these simple structures proved to be powerful enough, I have some open questions. Can you simultaneously reroot a tree and query LCA? Can you query both LCA and subtree sum? and so on. Of course, I don't want to lose the possibility to make link-cut operations (maybe without rerooting).

Summing up, I made a table with pros and cons of every approach.

Stores LCA Subtree sum Path sum Rerooting
1 edges + (values on edges) + + (not sure if works with sum)
2 vertices + (values on vertices) +
3 vertices + (no rerooting) + (no LCA)

So, the final question (and the main purpose of this post) is: can you add some  + 's to this table and/or tell about some other related methods?

P.S. This topic is by no means related to heavy-light decomposition and link-cut trees. I know that they may solve some proposed problems, but the idea is to squeeze as much as possible from Euler tours.

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

»
14 months ago, # |
  Vote: I like it +16 Vote: I do not like it

I think what you called "binary accent" is referenced as "binary lifting". Great article by the way! Thanks

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

What is the value of rerooting? What can we calculate with rerooting that we can't do otherwise?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can read it in the post 'There is also a trick to compute sum on path from root to a vertex'

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

Can anyone suggest nice problems relating to this topic ??

»
12 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Open-ended question Can we reroot a tree and be able to answer the LCA as well?

Answer is yes. This is exactly what this question asks ( https://www.codechef.com/problems/TALCA )

Here is a link to my implementation using the above technique ( https://www.codechef.com/viewsolution/10863340 )

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

Did you reach a conclusion regarding this, or is it still an interest?