Euler Tour Technique
Authors: Benjamin Qi, Andrew Wang, Neo Wang
Flattening a tree into an array to easily query and update subtrees.
Introduction
Focus Problem – try your best to solve this problem before continuing!
If we can preprocess a rooted tree such that every subtree corresponds to a contiguous range on an array, we can do updates and range queries on it!
Tutorial
Resources | ||||
---|---|---|---|---|
CPH | introduces tree traversal array, how to solve above problem | |||
SecondThread |
Implementation
Let's use the below graph for a quick demo of the technique:
Here's the code we're going to use to perform a Euler Tour on the graph. Notice that it follows the same general structure as a normal depth-first search. It's just that in this algorithm, we're keeping a few auxiliary variables we're going to use later on.
C++
#include <iostream>#include <vector>using std::vector;// The graph represented as an adjacency list (0-indexed)vector<vector<int>> neighbors{{1, 2}, {0}, {0, 3, 4}, {2}, {2}};vector<int> start(neighbors.size());vector<int> end(neighbors.size());int timer = 0;
Java
public class EulerTour {// The graph represented as an adjacency list (0-indexed)static int[][] neighbors = new int[][] {{1, 2}, {0}, {0, 3, 4}, {2}, {2}};static int[] start = new int[neighbors.length];static int[] end = new int[neighbors.length];static int timer = 0;static void eulerTour(int at, int prev) {start[at] = timer++;for (int n : neighbors[at]) {if (n != prev) { eulerTour(n, at); }}end[at] = timer;}}
Python
# The graph represented as an adjacency list (0-indexed)neighbors = [[1, 2], [0], [0, 3, 4], [2], [2]]start = [0] * len(neighbors)end = [0] * len(neighbors)timer = 0def euler_tour(at: int, prev: int):global timerstart[at] = timertimer += 1for n in neighbors[at]:if n != prev:euler_tour(n, at)end[at] = timer
Tour Walkthrough
Before the tour, our and arrays are initialized with zeros. In this visualization, the first row represents the node indices, the second row represents , and the third represents .
For brevity's sake, in this walkthrough, we're going to use instead of the full above function name.
Current timer value: 0
Node Index | 1 | 2 | 3 | 4 | 5 |
0 | 0 | 0 | 0 | 0 | |
0 | 0 | 0 | 0 | 0 |
Since we call , we set to the current timer value of . Then, we proceed to call and .
Current timer value: 1
Node Index | 1 | 2 | 3 | 4 | 5 |
0 | 0 | 0 | 0 | 0 | |
0 | 0 | 0 | 0 | 0 |
Now we must resolve and . It does not matter which order we process these in, so for this example, we start with . Since the timer value is 1, we set to 1 and increment the timer. However, because node has no children, we don't call . Instead, we set to 2 because our current timer is now 2.
Current timer value: 2
Node Index | 1 | 2 | 3 | 4 | 5 |
0 | 1 | 0 | 0 | 0 | |
0 | 2 | 0 | 0 | 0 |
Now we must resolve . Similar to before, we set to the value of the timer (2 in this case) and increment the timer. Then, we proceed to make the calls and .
Current timer value: 3
Node Index | 1 | 2 | 3 | 4 | 5 |
0 | 1 | 2 | 0 | 0 | |
0 | 2 | 0 | 0 | 0 |
Now we must resolve and . First, we resolve by setting to the value of the timer (3 in this case) and incrementing the timer. Then, since node has no children, set to 4.
Now the value of the timer is 4, and we must resolve . Similar to before, we set to 4. Since node also has no children, set to 5.
Current timer value: 5
Node Index | 1 | 2 | 3 | 4 | 5 |
0 | 1 | 2 | 3 | 4 | |
0 | 2 | 0 | 4 | 5 |
Now, we must resolve the remaining calls. We first encounter and resolve node , setting to 5. We then do the same for node , setting to 5. Our DFS traversal is now complete.
Node Index | 1 | 2 | 3 | 4 | 5 |
0 | 1 | 2 | 3 | 4 | |
5 | 2 | 5 | 4 | 5 |
Notice that after running , each range contains all ranges for each in the subtree of . Also, is equal to the subtree size of .
Here's a small animation of the tour if you're still confused:
Solution - Subtree Queries
C++
#include <algorithm>#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;Code Snippet: BIT (from PURS module) (Click to expand)
LCA
Focus Problem – try your best to solve this problem before continuing!
Focus Problem – try your best to solve this problem before continuing!
Tutorial
Resources | ||||
---|---|---|---|---|
CPH | ||||
cp-algo |
Implementation
Resources | ||||
---|---|---|---|---|
Benq |
C++
int n; // The number of nodes in the graphvector<int> graph[100000];int timer = 0, tin[100000], euler_tour[200000];int segtree[800000]; // Segment tree for RMQvoid dfs(int node = 0, int parent = -1) {tin[node] = timer; // The time when we first visit a nodeeuler_tour[timer++] = node;for (int i : graph[node]) {if (i != parent) {
Java
import java.io.*;import java.util.*;public class LCA {public static int[] euler_tour, tin;public static int timer, size, N;public static ArrayList<Integer> g[];// Segtree codepublic static final int maxsize = (int)1e7; // limit for array size
Sparse Tables
The above code does time preprocessing and allows LCA queries in time. If we replace the segment tree that computes minimums with a sparse table, then we do time preprocessing and query in time.
Focus Problem – try your best to solve this problem before continuing!
The following is an example implementation of a sparse table and code that answers LCA queries. Build time is , and queries are .
C++
#include <bits/stdc++.h>using namespace std;template <typename T> class SparseTable {private:int n, log2dist;vector<vector<T>> st;public:SparseTable(const vector<T> &v) {
Resources
Resources | ||||
---|---|---|---|---|
CPH | diagrams | |||
PAPS | code | |||
cp-algo |
Optional: Faster Preprocessing
From CPH:
There are also more sophisticated techniques where the preprocessing time is only , but such algorithms are not needed in competitive programming.
Ex. the following:
Implementation
C++
Resources | ||||
---|---|---|---|---|
Benq |
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSES | Easy | Show TagsEuler Tour, PURS | |||
CSES | Normal | Show TagsEuler Tour, PURS | |||
Gold | Normal | Show TagsEuler Tour, HLD, PURS | |||
Gold | Normal | Show TagsEuler Tour, LCA | |||
Platinum | Normal | Show TagsEuler Tour, PURS | |||
AC | Normal | Show TagsEuler Tour | |||
CF | Normal | Show TagsEuler Tour | |||
AC | Normal | Show TagsBinary Search, Euler Tour | |||
AC | Hard | Show TagsLCA, PURS | |||
IOI | Hard | Show TagsBinary Search, Euler Tour | |||
Platinum | Hard | Show TagsEuler Tour, Lazy SegTree, PURS | |||
DMOPC | Very Hard | Show TagsEuler Tour, PURS |
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!