Técnica del tour de Euler

Introducción

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Subtree Queries	Fácil	Euler Tour	en el módulo

Si preprocesamos un árbol enraizado de modo que cada subárbol corresponda a un rango contiguo de un arreglo, podemos hacer actualizaciones y consultas de rango sobre él.

Tutorial

Recursos
Fuente	Recurso	Notas
CPH	18.2 - Subtrees & Paths	introduce el arreglo de recorrido del árbol y cómo resolver el problema de arriba
SecondThread	Tree Basics - Tree Flattening

Implementación

Usemos el grafo de abajo para una demostración rápida de la técnica:

Este es el código que vamos a usar para hacer un tour de Euler sobre el grafo. Observar que sigue la misma estructura general que una búsqueda en profundidad normal. La diferencia es que en este algoritmo guardamos algunas variables auxiliares que vamos a usar más adelante.

C++JavaPython


#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;
 
void euler_tour(int at, int prev) {
	start[at] = timer++;
	for (int n : neighbors[at]) {
		if (n != prev) { euler_tour(n, at); }
	}
	end[at] = timer;
}


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;
	}
}


# 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 = 0
 
 
def euler_tour(at: int, prev: int):
	global timer
	start[at] = timer
	timer += 1
	for n in neighbors[at]:
		if n != prev:
			euler_tour(n, at)
	end[at] = timer

Recorrido del tour

Antes del tour, nuestros arreglos $\texttt{start}$ y $\texttt{end}$ se inicializan con ceros. En esta visualización, la primera fila representa los índices de los nodos, la segunda representa $\texttt{start}$ y la tercera representa $\texttt{end}$ .

Para abreviar, en este recorrido vamos a usar $\text{dfs}$ en lugar del nombre completo de la función de arriba.

Valor actual del timer: 0

Índice del nodo	1	2	3	4	5
$\texttt{start}$	0	0	0	0	0
$\texttt{end}$	0	0	0	0	0

Como llamamos $\text{dfs}(1, 0)$ , ponemos $\texttt{start}[1]$ en el valor actual del timer, $0$ . Después llamamos $\text{dfs}(2, 1)$ y $\text{dfs}(3, 1)$ .

Valor actual del timer: 1

Índice del nodo	1	2	3	4	5
$\texttt{start}$	0	0	0	0	0
$\texttt{end}$	0	0	0	0	0

Ahora hay que resolver $\text{dfs}(2, 1)$ y $\text{dfs}(3, 1)$ . El orden en que los procesemos no importa, así que en este ejemplo empezamos con $\text{dfs}(2, 1)$ . Como el valor del timer es 1, ponemos $\texttt{start}[2]$ en 1 e incrementamos el timer. Sin embargo, como el nodo $2$ no tiene hijos, no llamamos $\text{dfs}$ . En cambio, ponemos $\texttt{end}[2]$ en 2 porque nuestro timer actual ahora es 2.

Valor actual del timer: 2

Índice del nodo	1	2	3	4	5
$\texttt{start}$	0	1	0	0	0
$\texttt{end}$	0	2	0	0	0

Ahora hay que resolver $\text{dfs}(3, 1)$ . De forma similar, ponemos $\texttt{start}[3]$ en el valor del timer (2 en este caso) e incrementamos el timer. Después hacemos las llamadas $\text{dfs}(4, 3)$ y $\text{dfs}(5, 3)$ .

Valor actual del timer: 3

Índice del nodo	1	2	3	4	5
$\texttt{start}$	0	1	2	0	0
$\texttt{end}$	0	2	0	0	0

Ahora hay que resolver $\text{dfs}(4, 3)$ y $\text{dfs}(5, 3)$ . Primero resolvemos $\text{dfs}(4, 3)$ poniendo $\texttt{start}[4]$ en el valor del timer (3 en este caso) e incrementando el timer. Después, como el nodo $4$ no tiene hijos, ponemos $\texttt{end}[4]$ en 4.

Ahora el valor del timer es 4 y hay que resolver $\text{dfs}(5, 3)$ . De forma similar, ponemos $\texttt{start}[5]$ en 4. Como el nodo $5$ tampoco tiene hijos, ponemos $\texttt{end}[5]$ en 5.

Valor actual del timer: 5

Índice del nodo	1	2	3	4	5
$\texttt{start}$	0	1	2	3	4
$\texttt{end}$	0	2	0	4	5

Ahora hay que resolver las llamadas restantes $\texttt{end}[\text{node}] = \text{timer}$ . Primero encontramos y resolvemos el nodo $3$ , poniendo $\texttt{end}[3]$ en 5. Después hacemos lo mismo para el nodo $1$ , poniendo $\texttt{end}[1]$ en 5. Nuestro recorrido DFS ya está completo.

Índice del nodo	1	2	3	4	5
$\texttt{start}$	0	1	2	3	4
$\texttt{end}$	5	2	5	4	5

Observar que después de ejecutar $\text{dfs}$ , cada rango $[\texttt{start}[i], \texttt{end}[i]]$ contiene todos los rangos $[\texttt{start}[j], \texttt{end}[j]]$ para cada $j$ en el subárbol de $i$ . Además, $\texttt{end}[i]-\texttt{start}[i]$ es igual al tamaño del subárbol de $i$ .

Acá hay una animación corta del tour por si todavía hay dudas:

Solución - Subtree Queries

C++


#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{BIT (from PURS module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	void set(int ind, int val) { add(ind, val - arr[ind]); }
 
	void add(int ind, int val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip
 
vector<vector<int>> neighbors;
vector<int> start;
vector<int> end;
int timer = 0;
 
void euler_tour(int at, int prev) {
	start[at] = timer++;
	for (int n : neighbors[at]) {
		if (n != prev) { euler_tour(n, at); }
	}
	end[at] = timer;
}
 
int main() {
	int node_num;
	int query_num;
	std::cin >> node_num >> query_num;
 
	vector<int> vals(node_num);
	for (int &v : vals) { std::cin >> v; }
 
	neighbors.resize(node_num);
	for (int e = 0; e < node_num - 1; e++) {
		int n1, n2;
		std::cin >> n1 >> n2;
		neighbors[--n1].push_back(--n2);
		neighbors[n2].push_back(n1);
	}
 
	start.resize(node_num);
	end.resize(node_num);
	euler_tour(0, -1);
 
	BIT<long long> bit(node_num);
	for (int i = 0; i < node_num; i++) { bit.set(start[i], vals[i]); }
	for (int q = 0; q < query_num; q++) {
		int type;
		std::cin >> type;
		if (type == 1) {
			int node, val;
			std::cin >> node >> val;
			bit.set(start[--node], val);
		} else if (type == 2) {
			int node;
			std::cin >> node;
			long long end_sum = bit.pref_sum(end[--node] - 1);
			long long start_sum;
			if (start[node] == 0) {
				start_sum = 0;
			} else {
				start_sum = bit.pref_sum(start[node] - 1);
			}
			cout << end_sum - start_sum << '\n';
		}
	}
}

LCA

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Company Queries II	Fácil	LCA	Solución

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Distance Queries	Fácil	LCA	—

Tutorial

Recursos
Fuente	Recurso	Notas
CPH	18.3 - Least Common Ancestor (Method 2)
cp-algo	Reducing LCA to RMQ

Implementación

Recursos
Fuente	Recurso	Notas
Benq	LCA with RMQ

C++Java


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) {
			dfs(i, node);
			euler_tour[timer++] = node;
		}
	}
}
 
int mn_tin(int x, int y) {
	if (x == -1) return y;
	if (y == -1) return x;
	return (tin[x] < tin[y] ? x : y);
}
 
// Build the segment tree: run `build()` after running dfs`
void build(int node = 1, int l = 0, int r = timer - 1) {
	if (l == r) segtree[node] = euler_tour[l];
	else {
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);
		segtree[node] = mn_tin(segtree[node * 2], segtree[node * 2 + 1]);
	}
}
 
int query(int a, int b, int node = 1, int l = 0, int r = timer - 1) {
	if (l > b || r < a) return -1;
	if (l >= a && r <= b) return segtree[node];
	int mid = (l + r) / 2;
	return mn_tin(query(a, b, node * 2, l, mid), query(a, b, node * 2 + 1, mid + 1, r));
}
 
// Make sure you run $dfs` and `build()` before you run this
int lca(int a, int b) {
	if (tin[a] > tin[b]) swap(a, b);
	return query(tin[a], tin[b]);
}


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 code
	public static final int maxsize = (int)1e7;  // limit for array size
	public static int t[] = new int[maxsize];
 
	public static void update(int p, int value) {  // set value at position p
		for (t[p += size] = value; p > 1; p >>= 1) t[p >> 1] = mn_tin(t[p], t[p ^ 1]);
	}
	public static int query(int l,
	                        int r) {  // sum on interval [l, r) (0-INDEXED)
		int res = N;
		for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
			if ((l & 1) != 0) res = mn_tin(res, t[l++]);
			if ((r & 1) != 0) res = mn_tin(res, t[--r]);
		}
		return res;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine());
		N = Integer.parseInt(str.nextToken());
		int Q = Integer.parseInt(str.nextToken());
		int[] val = new int[N + 1];
		g = new ArrayList[N + 1];
		str = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) { g[i] = new ArrayList<Integer>(); }
		for (int i = 2; i <= N; i++) {
			int a = Integer.parseInt(str.nextToken());
			g[i].add(a);
			g[a].add(i);
		}
		euler_tour = new int[2 * N - 1];
		tin = new int[N + 1];
		dfs(1, 0);
		size = 2 * N - 1;
		for (int i = 0; i < 2 * N - 1; i++) { update(i, euler_tour[i]); }
		for (int i = 0; i < Q; i++) {
			str = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			System.out.println(lca(a, b));
		}
	}
	public static void dfs(int i, int p) {
		tin[i] = timer;
		euler_tour[timer++] = i;
		for (int next : g[i]) {
			if (next != p) {
				dfs(next, i);
				euler_tour[timer++] = i;
			}
		}
	}
	public static int lca(int a, int b) {
		if (tin[a] > tin[b]) {
			int temp = a;
			a = b;
			b = temp;
		}
		if (a == b) { return a; }
		return query(tin[a], tin[b]);
	}
	public static int mn_tin(int x, int y) {
		if (x == -1) return y;
		if (y == -1) return x;
		return (tin[x] < tin[y] ? x : y);
	}
}

Tablas Dispersas

El código de arriba hace preprocesamiento en $\mathcal{O}(N)$ y permite consultas de LCA en $\mathcal{O}(\log N)$ . Si reemplazamos el árbol de segmentos que calcula mínimos por una tabla dispersa (sparse table), entonces hacemos preprocesamiento en $\mathcal{O}(N\log N)$ y consultamos en $\mathcal{O}(1)$ .

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Static RMQ	Fácil		en el módulo

Lo siguiente es una implementación de ejemplo de una tabla dispersa y código que responde consultas de LCA. El tiempo de construcción es $\mathcal{O}(N\log N)$ , y las consultas son $\mathcal{O}(1)$ .

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) {
		n = (int)v.size();
		log2dist = 1 + (int)log2(n);
		st.resize(log2dist);
		st[0] = v;
		for (int i = 1; i < log2dist; i++) {
			st[i].resize(n - (1 << i) + 1);
			for (int j = 0; j + (1 << i) <= n; j++) {
				st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
			}
		}
	}
 
	/** @return minimum on the range [l, r] */
	T query(int l, int r) {
		int i = (int)log2(r - l + 1);
		return min(st[i][l], st[i][r - (1 << i) + 1]);
	}
};
 
class LCA {
  private:
	const int n;
	const vector<vector<int>> &adj;
	SparseTable<pair<int, int>> rmq;
	vector<int> tin, et, dep;
	int timer = 0;
 
	/** prepares tin, et, dep arrays */
	void dfs(int u, int p) {
		tin[u] = timer;
		et[timer++] = u;
		for (int v : adj[u]) {
			if (v == p) { continue; }
			dep[v] = dep[u] + 1;
			dfs(v, u);
			et[timer++] = u;
		}
	}
 
  public:
	// make sure the adjacency list is 0 indexed
	LCA(vector<vector<int>> &_adj)
	    : n((int)_adj.size()), adj(_adj), tin(n), et(2 * n), dep(n),
	      rmq(vector<pair<int, int>>(1)) {
		dfs(0, -1);
		vector<pair<int, int>> arr(2 * n);
		for (int i = 0; i < 2 * n; i++) { arr[i] = {dep[et[i]], et[i]}; }
		rmq = SparseTable<pair<int, int>>(arr);
	}
 
	/** @return LCA of nodes a and b */
	int query(int a, int b) {
		if (tin[a] > tin[b]) { swap(a, b); }
		return rmq.query(tin[a], tin[b]).second;
	}
};

Recursos

Recursos
Fuente	Recurso	Notas
CPH	9.1 - Minimum Queries	diagramas
PAPS	11.2.2 - Sparse Tables	código
cp-algo	Sparse Table

Preprocesamiento más rápido

De CPH:

También hay técnicas más sofisticadas en las que el tiempo de preprocesamiento es solo $\mathcal{O}(N)$ , pero esos algoritmos no se necesitan en programación competitiva.

Por ejemplo, lo siguiente:

CF: $\mathcal{O}(1)$ Query RMQ with $\mathcal{O}(N)$ build

Implementación

C++

Recursos
Fuente	Recurso	Notas
Benq	RMQ

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Distinct Colors	Fácil	Euler Tour, PURS	Solución
CSES	Path Queries	Normal	Euler Tour, PURS	Solución
Gold	Cow Land	Normal	Euler Tour, PURS, HLD	Solución
Gold	Milk Visits	Normal	Euler Tour, LCA	Solución
Platinum	Promotion Counting	Normal	Euler Tour, PURS	Solución
AC	Exactly K Steps	Normal	Euler Tour	—
CF	The Shortest Statement	Normal	Euler Tour	Solución
AC	Count Descendants	Normal	Euler Tour, Binary Search	—
AC	★ Distance Queries on a Tree	Normal	LCA, PURS	Solución
IOI	2009 - Regions	Difícil	Euler Tour, Binary Search	Solución
Platinum	Bessie's Snow Cow	Difícil	Euler Tour, PURS, Lazy SegTree	Solución
DMOPC	Victor Takes Over Canada	Muy difícil	Euler Tour, PURS	—