Euler Tour

EulerTour maps every subtree of a tree to a contiguous preorder interval [tin[v], tout[v]).

Supported graph forms

The primary interface accepts a sequence-backed Nim-ACL Graph.

A lightweight seq[seq[int]] adjacency list is accepted by the same constructor. Both forms share one traversal implementation, and the source graph is not retained.

Import

import atcoder/extra/graph/graph_template
import atcoder/extra/graph/euler_tour

API

proc initEulerTour*[G](
  graph: G,
  root: int = 0
): EulerTour

proc subtreeRange(
  tour: EulerTour,
  vertex: int
): tuple[l, r: int]

proc subtreeSize(
  tour: EulerTour,
  vertex: int
): int

Example: Nim-ACL Graph

import atcoder/extra/graph/graph_templateimport atcoder/extra/graph/euler_tourvar graph = initGraph(5)graph.addBiEdge(0, 1)graph.addBiEdge(0, 2)graph.addBiEdge(1, 3)graph.addBiEdge(1, 4)let tour = initEulerTour(graph)doAssert tour.subtreeSize(1) == 3

Example: adjacency list

import atcoder/extra/graph/euler_tourvar graph = newSeq[seq[int]](5)proc addEdge(u, v: int) =  graph[u].add v  graph[v].add uaddEdge(0, 1)addEdge(0, 2)addEdge(1, 3)addEdge(1, 4)let tour = initEulerTour(graph)doAssert tour.subtreeSize(1) == 3

Complexity

build: O(n)
subtree interval: O(1)
memory: O(n)