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}[1]$ 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}[2]$ to 1 and increment the timer. However, because node $2$ has no children, we don't call $\text{dfs}$. Instead, we set $\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 $\text{dfs}(3, 1)$. Similar to before, we set $\texttt{st}[3]$ 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}[4]$ to the value of the timer (3 in this case) and incrementing the timer. Then, since node $4$ has no children, set $\texttt{en}[4]$ 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}[5]$ to 4. Since node $5$ also has no children, set $\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 $\texttt{en}[\text{node}] = \text{timer} - 1$ calls. We first encounter and resolve node $3$, setting $\texttt{en}[3]$ to 4. We then do the same for node $1$, setting $\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] 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[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 – 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[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 $\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-Tree, PURS
GoldNormal
Show TagsEuler-Tree, HLD, PURS
GoldNormal
Show TagsEuler-Tree, LCA
PlatNormal
Show TagsEuler-Tree, PURS
ACNormal
Show TagsBinary Search, Euler Tour
IOIHard
Show TagsBinary Search, Euler-Tree
PlatHard
Show TagsEuler-Tree, PURS
CFHard
Show TagsEuler Tour, RURQ
DMOJVery Hard
Show TagsEuler-Tree, 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!