Not Frequent
0/14

# 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

### Implementation

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

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:

Before the DFS, our $\texttt{st}$ and $\texttt{en}$ arrays are initialized with zeros. In this visualization, the first row represents the node indices, the second row represents $\texttt{st}$, and the third represents $\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 $\text{dfs}(1, 0)$, we set $\texttt{st}$ to the current timer value of $0$. Then, we proceed to call $\text{dfs}(2, 1)$ and $\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 $\text{dfs}(2, 1)$ and $\text{dfs}(3, 1)$. It does not matter which order we process these in, so for this example, we start with $\text{dfs}(2, 1)$. Since the timer value is 1, we set $\texttt{st}$ to 1 and increment the timer. However, because node $2$ has no children, we don't call $\text{dfs}$. Instead, we set $\texttt{en}$ 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 $\text{dfs}(3, 1)$. Similar to before, we set $\texttt{st}$ to the value of the timer (2 in this case) and increment the timer. Then, we proceed to make the calls $\text{dfs}(4, 3)$ and $\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 $\text{dfs}(4, 3)$ and $\text{dfs}(5, 3)$. First, we resolve $\text{dfs}(4, 3)$ by setting $\texttt{st}$ to the value of the timer (3 in this case) and incrementing the timer. Then, since node $4$ has no children, set $\texttt{en}$ to 3.

Now the value of the timer is 4, and we must resolve $\text{dfs}(5, 3)$. Similar to before, we set $\texttt{st}$ to 4. Since node $5$ also has no children, set $\texttt{en}$ 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 $\texttt{en}[\text{node}] = \text{timer} - 1$ calls. We first encounter and resolve node $3$, setting $\texttt{en}$ to 4. We then do the same for node $1$, setting $\texttt{en}$ to 4. Our DFS traversal is now complete.

 Node Index 1 2 3 4 5 st[i] 0 1 2 3 4 en[i] 4 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==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 – try your best to solve this problem before continuing!

Focus Problem – try your best to solve this problem before continuing!

Resources
CPH
cp-algo

### Implementation

Resources
Benq

C++

int n; // The number of nodes in the graphvector<int> graph;int timer = 0, tin, euler_tour;int segtree; // 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 $\mathcal{O}(N)$ time preprocessing and allows LCA queries in $\mathcal{O}(\log N)$ time. If we replace the segment tree that computes minimums with a sparse table, then we do $\mathcal{O}(N\log N)$ time preprocessing and query in $\mathcal{O}(1)$ time.

Focus Problem – try your best to solve this problem before continuing!

Resources
CPH

diagrams

PAPS

code

cp-algo

### Optional: Faster Preprocessing

From CPH:

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

Ex. the following:

C++

Resources
Benq

## Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsEuler Tour, PURS
CSESNormal
Show TagsEuler Tour, PURS
GoldNormal
Show TagsEuler Tour, HLD, PURS
GoldNormal
Show TagsEuler Tour, LCA
PlatNormal
Show TagsEuler Tour, PURS
ACNormal
Show TagsBinary Search, Euler Tour
IOIHard
Show TagsBinary Search, Euler Tour
PlatHard
Show TagsEuler Tour, Lazy SegTree, PURS
CFHard
Show TagsEuler Tour, RURQ
DMOJVery Hard
Show TagsEuler Tour, PURS

### 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!