木のオイラーツアー
グラフ理論の木の表現方法の1つ。
「根から全ての辺を2回ずつ通って根に帰ってくる」パスを指す。
少し混同しやすい語として、グラフで「オイラー路（Eulerian Trail）」というと、全ての辺を1度ずつ通るパスを指す。
オイラーツアーは、木の無向辺それぞれを、双方向の2本の有向辺に変換したグラフ上でのオイラー路、とも言える。
文脈によっては、パスで訪れる頂点や辺の番号を順に記録した列そのものを指すこともある。
⓪ オイラーツアーの頂点通過順
a／b|＼c 0,1,4,5,4,6,4,1,0,2,0,3,7,3,8,3,0
① ② ③
d｜ e/\f オイラーツアーの辺通過順
④ ⑦⑧ a,d,g,g,h,h,d,a,b,b,c,e,e,f,f,c
g/\h （または、ツアーを開始・終了することを示す便宜的な値を加えて）
⑤⑥ X,a,d,g,g,h,h,d,a,b,b,c,e,e,f,f,c,X
利点
こんな表現をして何が嬉しいか？
一般に、木に対するクエリ問題は更新に弱い。
頂点や辺が何らかの値を持っていて、パスや部分木の合計値といった取得クエリのみが飛んでくる場合には、
前計算で高速に対応できることもある。
しかし、値の更新クエリもある場合、その反映も同時にこなすのは、なかなか難しい。
オイラーツアーは、木構造を列で表現するため、セグメント木など「列」に対する便利なデータ構造を適用できる。
それによって、更新も取得も $O(\log{N})$ とかでできるような状態の持ち方ができる。
他に同様の利点があるデータ構造に、上記のリンクにもあるが HL分解 がある。
性質
部分木を列の連続区間で表せる
1辺を2回通るということは、行くときと帰るときで2回使われるので、他に無駄な往復はできない。
ある頂点 $v$ を根とする部分木に注目すると、以下のようにするしかない。
なので、オイラーツアーでは、部分木は列の連続区間として現れるし、異なる部分木は互いに交わらない。
⓪ オイラーツアーの頂点通過順
a／b|＼c 0,1,4,5,4,6,4,1,0,2,0,3,7,3,8,3,0
① ② ③ ~~~~~~~~~~~~~ ~~~~~~~~~
d｜ e/\f ①を根とする ③を根とする
④ ⑦⑧ 部分木の 部分木の
g/\h オイラーツアー オイラーツアー
⑤⑥
特に、各頂点が最初に現れる $in[v]$ と最後に現れる $out[v]$ を前計算しておけば、
その区間 $[in[v], out[v]]$ が、$v$ を根とする部分木を表す区間となる。
オイラーツアーで解ける問題例
大きく分けて、セグメント木で管理する実装と、split-mergeが可能な $n$ 分木（平衡二分木など）で管理する実装がある。
$n$ 分木では実装が複雑ながら、辺の追加・削除といった更新にも対応できる。
更新クエリ（セグメント木・遅延評価セグメント木）
頂点・辺に値を加算・値で更新
部分木内の頂点・辺に一定値を加算
例題
実装例
頂点や辺に値はあるか、何を更新して何を求めたいか、によって必要な情報がちょっとずつ異なり、
汎用的なライブラリに落とし込みにくいのよね。
LCA（最小共通祖先）
問題設定
必要な前計算データ
sgt_depths: オイラーツアー頂点順の (深さ, 頂点番号) のタプル列を、区間最小値を取得できるセグメント木に載せたもの
first_appear: 各頂点がオイラーツアー上で最初に出てくるindex
原理とかは、冒頭で挙げたサイトで図付きで説明されているので割愛。
sgt_depths上で $first\_appear[u] ～ first\_appear[v]$ の区間最小値を取得して、その頂点番号がLCA。$first\_appear[u] > first\_appear[v]$ の場合もあるので順番に注意。
なお、この問題はダブリングで解くこともできる。（最小共通祖先）
Python3
class LcaEulerTour:
"""
※別途、セグメント木クラスをこれより前に記述し、SEGTREE_CLSに与えてください。
想定するメンバ関数:
instance = SEGTREE_CLS.from_array(配列, 単位元の生成関数, 二項演算関数) ... 配列からインスタンスの生成
instance.get_range(l, r) ... [l,r)の区間取得
オイラーツアーにより最小共通祖先を求める
"""
SEGTREE_CLS = SegmentTree
def __init__(self, n: int, links: List[List[int]], root: int = 0):
"""
:param n: 頂点数
:param links: links[u] = [v1, v2, ...] uからつながる辺のリスト のリスト
:param root: 根とする頂点
"""
self.n = n
self.links = links
self.root = root
progress = [0] * n
depths = [-1] * n
parents = [-1] * n
depths[root] = 0
euler_tour = [root]
v = root
while v != root or progress[root] < len(links[root]):
if progress[v] >= len(links[v]):
v = parents[v]
euler_tour.append(v)
continue
u = links[v][progress[v]]
progress[v] += 1
if u == parents[v]:
continue
euler_tour.append(u)
depths[u] = depths[v] + 1
parents[u] = v
v = u
# 出現位置の計算
first_appear = [-1] * n
for i, v in enumerate(euler_tour):
if first_appear[v] == -1:
first_appear[v] = i
self.euler_tour = euler_tour
self.depths = depths
self.parents = parents
self.first_appear = first_appear
# セグメント木の構築
INF = 1 << 60
depths_with_vertex = [(depths[v], v) for v in euler_tour]
self.segment_tree_depth = self.SEGTREE_CLS.from_array(depths_with_vertex, lambda: (INF, -1), min)
def get_lca(self, u: int, v: int):
fau = self.first_appear[u]
fav = self.first_appear[v]
if fau > fav:
fau, fav = fav, fau
_, lca = self.segment_tree_depth.get_range(fau, fav + 1)
return lca
n = int(input())
links = [[] for _ in range(n)]
for i in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
links[u].append(v)
links[v].append(u)
lca_eular = LcaEulerTour(n, links)
# クエリへの応答
q = int(input())
for _ in range(q):
u, v = map(int, input().split())
u -= 1
v -= 1
lca = lca_eular.get_lca(u, v)
print(lca)
Input:
9
1 2
1 3
1 4
2 5
4 8
4 9
5 6
5 7
4
8 9
5 8
2 7
3 3
①
／｜＼
② ③ ④
｜ /\
⑤ ⑧⑨
/\
⑥⑦
Output:
4
1
2
3