beet's soil

競プロのことなど

2種類のEuler Tourについて

メモ

オイラーツアーとは?

オイラーツアーは頂点/辺からインデックスへの写像を与えるデータ構造
「木上の区間」と「インデックスの区間」がうまく対応するように写像を選ぶと、
いろいろなクエリが処理できる

頂点属性のオイラーツアー

github.com

蟻本に載ってない方 でもこっちの方が有名な気がする(謎)
部分木に関するクエリが処理できる

仕組みはかなりシンプルで、in-orderなりでDFSして頂点を訪れるたびにindexを振るだけ

void dfs(int v,int p,int &idx){
  ls[v]=idx++;
  for(int u:G[v])
    if(u!=p) dfs(u,v,idx);
  rs[v]=idx;
}

とすると、vの部分木に区間[ls[v], rs[v])が対応する

問題例:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2871&lang=jpjudge.u-aizu.ac.jp

辺属性のオイラーツアー

github.com

蟻本に載ってる方(第2版 p. 295) パスに関するクエリを処理できる 

  • 辺を逆にたどると打ち消す(可逆性)

- 辺の順序を無視できる(可換性)
必要があるので要件としてはアーベル群くらい
(追記)
よしなにやれば可換性はいらない(u-vパスを求めるのに演算の順方向と逆方向持てばいけそう)
仮定しておくと楽 正則行列の積とかで出なくはない… のか?
まで書いたら問題思い出しちゃった https://yukicoder.me/problems/no/650
(さらに追記)これ正則性保証されてないのでオイラーツアーでは無理です(うく)


HL分解があればいらない気もするけどこっちの方がlogが一個少ない

こっちも実装はシンプルで

void dfs(int v,int p,int &idx){
  dep[v]=d;
  for(int u:G[v]){
    if(u==p) continue;
    ds[u]=idx++;
    dfs(u,v,idx);
    us[u]=idx++;
  }
}

とすると、vの親とvの間の辺eに対して、ds[v]がeを降りること、us[v]がeを上がることに対応する
初期化や更新のときはds[v]に元の辺の値、us[v]に逆元を割り当てることになる

区間として取れるのは上から下に降りるようなパスだけなので、
一般のu-vクエリに対してはr=LCA(u,v)として r-uパスとr-vパスの和を求める必要がある

上から下に降りるようなu-vパスは区間[ds[u]+1, ds[v]+1)に対応する
(ds[u]がuに降りてくる辺なのでそれは含めてはいけない)

問題例:
atcoder.jp

おまけ

HL分解ならモノイドでOK つよい
beet-aizu.hatenablog.com

↓これ↓をすると部分木クエリも捌ける 最強じゃん
codeforces.com

問題例:
atcoder.jp

感想

辺属性を書いたはいいけど定数倍が微妙すぎて扱いに困る ウケ