はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるオイラーツアー問題まとめ

オイラーツアー

  • 木をDFSしたときの順番で頂点を記録する手法
    • pre-order : 頂点に到着したら記録
    • post-order : 頂点から離れるときに記録
  • 用途
    • 根付き木のある頂点からの部分木に対するクエリを処理
    • ある頂点がある頂点の部分木に含まれるかを高速に判定する
    • 上手くオイラーツアーを作るとパスのコストの総和が取れる
  • 木をBFSしたときの順番で頂点を記録するBFS Euler Tourというのもある
    • オイラーツアーのbfs-order
    • 用途としては、ある頂点から一定の距離にある頂点に対して区間操作を行える

問題

オイラーツアーっぽくやる問題