TL;DR: is it possible to construct an Euler tour tree which supports LCA, subtree sum and rerooting?
Euler tour 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.
The first way is to write down all edges of the tree, directed, in order of DFS. This is how Euler tour 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 descent into it and when we leave it.
1
/ \
2 5
/ \
3 4
1 2 3 3 4 4 2 5 5 1