PrevNext
Not Frequent
 0/11

Euler Tour Technique

Authors: Benjamin Qi, Andi Qu, Andrew Wang, Neo Wang

Flattening a tree into an array to easily query and update subtrees.

Introduction

Focus Problem – read through 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

After running dfs()\text{dfs}(), each range [st[i],en[i]][\texttt{st}[i], \texttt{en}[i]] contains all ranges [st[j],en[j]][\texttt{st}[j], \texttt{en}[j]] for each jj in the subtree of ii. Also, en[i]st[i]+1\texttt{en}[i]-\texttt{st}[i]+1 is equal to the subtree size of ii.

C++

const int MX = 2e5+5;
vector<int> adj[MX];
int timer = 0, st[MX], en[MX];
void dfs(int node, int parent) {
st[node] = timer++;
for (int i : adj[node]) {
if (i != parent) {
dfs(i, node);
}
}
en[node] = timer-1;
}

Java

public static void dfs(int i, int p) {
st[i] = timer++;
for (int next : g[i]) {
if(next != p) dfs(next, i);
}
en[i] = timer-1;
}

Example Input

5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3

Our example input corresponds to the following graph:

1

2

5

4

3

Before the DFS, our st\texttt{st} and en\texttt{en} arrays are initialized with zeros. In this visualization, the first row represents the node indices, the second row represents st\texttt{st}, and the third represents en\texttt{en}.

Current timer value: 0

Node Index 1 2 3 4 5
st[i] 0 0 0 0 0
en[i] 0 0 0 0 0

Since we call dfs(1,0)\text{dfs}(1, 0), we set st[1]\texttt{st}[1] to the current timer value of 00. Then, we proceed to call dfs(2,1)\text{dfs}(2, 1) and dfs(3,1)\text{dfs}(3, 1).

Current timer value: 1

Node Index 1 2 3 4 5
st[i] 0 0 0 0 0
en[i] 0 0 0 0 0

Now we must resolve dfs(2,1)\text{dfs}(2, 1) and dfs(3,1)\text{dfs}(3, 1). It does not matter which order we process these in, so for this example, we start with dfs(2,1)\text{dfs}(2, 1). Since the timer value is 1, we set st[2]\texttt{st}[2] to 1 and increment the timer. However, because node 22 has no children, we don't call dfs\text{dfs}. Instead, we set en[2]\texttt{en}[2] to 1 because our current timer is now 2.

Current timer value: 2

Node Index 1 2 3 4 5
st[i] 0 1 0 0 0
en[i] 0 1 0 0 0

Now we must resolve dfs(3,1)\text{dfs}(3, 1). Similar to before, we set st[3]\texttt{st}[3] to the value of the timer (2 in this case) and increment the timer. Then, we proceed to make the calls dfs(4,3)\text{dfs}(4, 3) and dfs(5,3)\text{dfs}(5, 3).

Current timer value: 3

Node Index 1 2 3 4 5
st[i] 0 1 2 0 0
en[i] 0 1 0 0 0

Now we must resolve dfs(4,3)\text{dfs}(4, 3) and dfs(5,3)\text{dfs}(5, 3). First, we resolve dfs(4,3)\text{dfs}(4, 3) by setting st[4]\texttt{st}[4] to the value of the timer (3 in this case) and incrementing the timer. Then, since node 44 has no children, set en[4]\texttt{en}[4] to 3.

Now the value of the timer is 4, and we must resolve dfs(5,3)\text{dfs}(5, 3). Similar to before, we set st[5]\texttt{st}[5] to 4. Since node 55 also has no children, set en[5]\texttt{en}[5] to 4.

Current timer value: 5

Node Index 1 2 3 4 5
st[i] 0 1 2 3 4
en[i] 0 1 0 3 4

Now, we must resolve the remaining en[node]=timer1\texttt{en}[\text{node}] = \text{timer} - 1 calls. We first encounter and resolve node 33, setting en[3]\texttt{en}[3] to 4. We then do the same for node 11, setting en[1]\texttt{en}[1] to 4. Our DFS traversal is now complete.

Node Index 1 2 3 4 5
st[i] 0 1 2 3 4
en[i] 5 1 4 3 4

Solution - Subtree Queries

Assumes that dfs() code is included. Uses a segment tree.

C++

/**
* Description: 1D point update, range query where \texttt{comb} is
* any associative operation. If $N=2^p$ then \texttt{seg[1]==query(0,N-1)}.
* Time: O(\log N)
* Source:
* http://codeforces.com/blog/entry/18051
* KACTL
* Verification: SPOJ Fenwick
*/

Java

import java.util.*;
import java.io.*;
public class Main {
public static int[] st;
public static int[] en;
public static int timer, n;
public static ArrayList<Integer> g[];
//Segtree code

LCA

Focus Problem – read through this problem before continuing!

Focus Problem – read through this problem before continuing!

Tutorial

Implementation

Resources
Benq

C++

int n; // The number of nodes in the graph
vector<int> graph[100000];
int timer = 0, tin[100000], euler_tour[200000];
int segtree[800000]; // Segment tree for RMQ
void dfs(int node = 0, int parent = -1) {
tin[node] = timer; // The time when we first visit a node
euler_tour[timer++] = node;
for (int i : graph[node]) {
if (i != parent) {

Java

import java.util.*;
import java.io.*;
public class LCA {
public static int[] euler_tour, tin;
public static int timer, size, N;
public static ArrayList<Integer> g[];
//Segtree code
public static final int maxsize = (int)1e7; // limit for array size

Sparse Tables

The above code does O(N)\mathcal{O}(N) time preprocessing and allows LCA queries in O(logN)\mathcal{O}(\log N) time. If we replace the segment tree that computes minimums with a sparse table, then we do O(NlogN)\mathcal{O}(N\log N) time preprocessing and query in O(1)\mathcal{O}(1) time.

Focus Problem – read through this problem before continuing!

Resources

Optional: Faster Preprocessing

From CPH:

There are also more sophisticated techniques where the preprocessing time is only O(N)\mathcal{O}(N), but such algorithms are not needed in competitive programming.

Ex. the following:

Implementation

C++

Resources
Benq

Problems

StatusSourceProblem NameDifficultyTags
CSESNormal
Show TagsEuler-Tree, PURS
GoldNormal
Show TagsEuler-Tree, HLD, PURS
GoldNormal
Show TagsEuler-Tree, LCA
PlatNormal
Show TagsEuler-Tree, PURS
IOIHard
Show TagsBinary Search, Euler-Tree
PlatHard
Show TagsEuler-Tree, PURS
DMOJVery Hard
Show TagsEuler-Tree, 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!

PrevNext