Nim-ACL

Euler Tour

EulerTour は、木をDFSし、各subtreeをpreorder上の連続区間へ変換するutilityです。

頂点 v のsubtreeは半開区間 [tin[v], tout[v]) に対応します。この区間をFenwick TreeやSegment Treeへ渡すことで、subtree queryを通常の区間queryへ変換できます。

対応するグラフ形式

標準的な形式として、sequence-backedなNim-ACL Graph に対応します。

軽量な隣接リスト seq[seq[int]] も同じ initEulerTour へ渡せます。両形式は同じDFS実装を利用し、構築後の EulerTour は入力graphを保持しません。

import

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

ローカル短縮import：

import lib/graph/graph_template
import lib/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

proc subtreeVertices(
  tour: EulerTour,
  vertex: int
): seq[int]

proc isAncestor(
  tour: EulerTour,
  ancestor, descendant: int
): bool

使用例：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) == 3let interval = tour.subtreeRange(1)doAssert interval.r - interval.l == 3

使用例：軽量な隣接リスト

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

計算量

頂点数を n とすると、

注意