Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

ifsmirnov's blog

By ifsmirnov, history, 6 years ago,

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.

• +97

 » 5 years ago, # |   +16 I think what you called "binary accent" is referenced as "binary lifting". Great article by the way! Thanks
 » 5 years ago, # |   +5 What is the value of rerooting? What can we calculate with rerooting that we can't do otherwise?
•  » » 5 years ago, # ^ |   0 You can read it in the post 'There is also a trick to compute sum on path from root to a vertex'
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -8 Can you explain uses of rerooting.
 » 5 years ago, # |   0 Can anyone suggest nice problems relating to this topic ??
•  » » 5 years ago, # ^ |   0 Recently appeared on codechef: CLOSEFAR
•  » » 5 years ago, # ^ |   +3 This one is nice 620E. New Year Tree
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 You can also pick any problem about LCA to practice this topic, like SPOJ LCA
 » 5 years ago, # |   -16 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 years ago, # ^ |   +20 Your implementation has nothing to do with Euler-Tour trees.
•  » » 5 years ago, # ^ |   +14 Answering your own question , never seen that before xD
 » 4 years ago, # |   0 Did you reach a conclusion regarding this, or is it still an interest?
 » 3 years ago, # |   0 We can store vertexes and edges at the same time by adding an edge (v,v) for each vertex v. That way we can finish the table above. But we still can't support both LCA and Rerooting. Maybe we need to rebuild the array h after rerooting. It doesn't matter. We can use rerooting and the trick "compute sum on path from root to a vertex" instead of querying LCA at most cases.
 » 3 years ago, # |   +3 Approach 2 is described in this paper (https://arxiv.org/pdf/1502.05292.pdf) as "depth-first-tour trees". It describes how you can do LCA in O(log n) with that approach, and you can reroot the tree to a neighbor of the root in O(log n) (described as the "evert" operation).Something that should be noted is that there's a typo in this paper: Lemma 17 should say s1+s2 in both cases, instead of saying s1+s1 in the second case.
 » 2 months ago, # |   +14 Very Informative, thanks!