Not Frequent
0/11

# Euler Tour Technique

Authors: Benjamin Qi, Andi Qu, Andrew Wang

### Prerequisites

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
CPHintroduces tree traversal array, how to solve above problem

### Implementation

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

C++

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

Java

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

### This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

example input

### Solution - Subtree Queries

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

C++

1/**2 * Description: 1D point update, range query where \texttt{comb} is3    * any associative operation. If $N=2^p$ then \texttt{seg==query(0,N-1)}.4 * Time: O(\log N)5 * Source: 6    * http://codeforces.com/blog/entry/180517    * KACTL8 * Verification: SPOJ Fenwick9 */10


Java

1import java.util.*;2import java.io.*;3
4public class Main {5    public static int[] st;6    public static int[] en;7    public static int timer, n;8    public static ArrayList<Integer> g[];9   10    //Segtree code

## LCA

Focus Problem – read through this problem before continuing!

Focus Problem – read through this problem before continuing!

Resources
CPH
cp-algo

### Implementation

Resources
Benq

C++

1int n; // The number of nodes in the graph2vector<int> graph;3int timer = 0, tin, euler_tour;4int segtree; // Segment tree for RMQ5
6void dfs(int node = 0, int parent = -1) {7    tin[node] = timer; // The time when we first visit a node8    euler_tour[timer++] = node;9    for (int i : graph[node]) {10        if (i != parent) {

Java

1import java.util.*;2import java.io.*;3
4public class LCA {5    public static int[] euler_tour, tin;6    public static int timer, size, N;7    public static ArrayList<Integer> g[];8   9    //Segtree code10    public static final int maxsize = (int)1e7;  // limit for array size

## Sparse Tables

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

Focus Problem – read through this problem before continuing!

### Resources

Resources
CPHdiagrams
PAPScode
cp-algo
Optional: Faster Preprocessing

From CPH:

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

Ex. the following:

C++

Resources
Benq

## Problems

StatusSourceProblem NameDifficultyTagsSolution
CSESNormal
Show Tags

Euler-Tree, PURS

GoldNormal
Show Tags

Euler-Tree, PURS, HLD

GoldNormal
Show Tags

Euler-Tree, LCA

External Sol
PlatNormal
Show Tags

Euler-Tree, PURS

External Sol
IOIHard
Show Tags

Euler-Tree, Binary Search

External Sol
PlatHard
Show Tags

Euler-Tree, PURS

External Sol
DMOJVery Hard
Show Tags

Euler-Tree, PURS

Check DMOJ