Flattening a tree
Many tree problems become easier if the tree is laid out in a line. The Euler tour records the order in which a depth first search enters and leaves each node, turning the tree into a flat sequence.
Entry and exit times
Run a depth first search from the root. For each node store two numbers:
- An entry time when the search first reaches the node.
- An exit time when the search finishes all its descendants.
The key property is that a node and all of its descendants occupy a contiguous range between that node's entry and exit times. So the subtree of any node maps cleanly onto an interval of the flattened array.
Why this helps
Once subtrees are intervals, subtree updates and subtree sums become range operations on an array. You can lay a segment tree or a Fenwick tree over the tour and answer subtree questions with standard range tools. A different variant that records each node on both entry and exit supports path queries as well.
Key idea
Store entry and exit times from a depth first search so each subtree becomes a contiguous array range answerable by range data structures.