木のオイラーツアー

グラフ理論の木の表現方法の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

利点

こんな表現をして何が嬉しいか？

一般に、木に対するクエリ問題は更新に弱い。

絶対に初心者でもわかるHL分解/Heavy-Light-Decomposition - Qiita

頂点や辺が何らかの値を持っていて、パスや部分木の合計値といった取得クエリのみが飛んでくる場合には、前計算で高速に対応できることもある。
しかし、値の更新クエリもある場合、その反映も同時にこなすのは、なかなか難しい。

オイラーツアーは、木構造を列で表現するため、セグメント木など「列」に対する便利なデータ構造を適用できる。
それによって、更新も取得も $O(\log{N})$ とかでできるような状態の持ち方ができる。

他に同様の利点があるデータ構造に、上記のリンクにもあるが HL分解がある。

性質

部分木を列の連続区間で表せる

1辺を2回通るということは、行くときと帰るときで2回使われるので、他に無駄な往復はできない。

ある頂点 $v$ を根とする部分木に注目すると、以下のようにするしかない。

① 部分木に入る（$v$ の親→$v$ の辺を通過、1回目）
② 部分木の全ての頂点をオイラーツアーで巡る
③ 部分木を出ていく（$v$→$v$ の親の辺を通過、2回目）

なので、オイラーツアーでは、部分木は列の連続区間として現れるし、異なる部分木は互いに交わらない。

    ⓪        オイラーツアーの頂点通過順
 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$ 分木では実装が複雑ながら、辺の追加・削除といった更新にも対応できる。

取得クエリ
- 根から $v$ までのパスに含まれる頂点・辺の値の合計
- $v$ を根とする部分木内の頂点・辺の値の合計
- 最小共通祖先（LCA, Lowest Common Ancestor）

更新クエリ（セグメント木・遅延評価セグメント木）
- 頂点・辺に値を加算・値で更新
- 部分木内の頂点・辺に一定値を加算
例題
- Library Checker - Vertex Add Subtree Sum

更新クエリ（$n$ 分木）
- （上記に加え、）
- 辺の追加（元の状態は森であり、クエリ時点で同じ連結成分内にある2頂点間に辺は張られない前提）
- 辺の削除
例題
- Library Checker - Dynamic Tree Vertex Add Subtree Sum

実装例

頂点や辺に値はあるか、何を更新して何を求めたいか、によって必要な情報がちょっとずつ異なり、汎用的なライブラリに落とし込みにくいのよね。

LCA（最小共通祖先）

問題設定

$N$ 頂点の木が与えられる（頂点番号は $1～N$）
$Q$ 個のクエリが与えられる
- $i$ 番目のクエリでは、頂点 $u_i,v_i$ の最小共通祖先を求めよ

必要な前計算データ

sgt_depths: オイラーツアー頂点順の (深さ, 頂点番号) のタプル列を、区間最小値を取得できるセグメント木に載せたもの
first_appear: 各頂点がオイラーツアー上で最初に出てくるindex
- （最初でなくても、どこかしらの出現indexであればよい）

原理とかは、冒頭で挙げたサイトで図付きで説明されているので割愛。

（再掲）
- Euler Tour のお勉強 | maspyのHP
- オイラーツアーした木に対するクエリ - Qiita

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:

    ①
  ／｜＼
 ② ③ ④
 ｜    /\
 ⑤   ⑧⑨
 /\
⑥⑦

Output:

目次

木のオイラーツアー

利点

性質

部分木を列の連続区間で表せる

オイラーツアーで解ける問題例

実装例

LCA（最小共通祖先）