メモ
2020/08/22 追記
ということなので気を付けてください
（まあ僕はこれからもオイラーツアーって呼び続けそうな気がしますが）
オイラーツアーとは？
(競技プログラミングにおける)オイラーツアーは頂点／辺からインデックスへの写像を与えるデータ構造
「木上の区間」と「インデックスの区間」がうまく対応するように写像を選ぶと、
いろいろなクエリが処理できる
頂点属性のオイラーツアー
蟻本に載ってない方 でもこっちの方が有名な気がする（謎）
部分木に関するクエリが処理できる
仕組みはかなりシンプルで、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
辺属性のオイラーツアー
蟻本に載ってる方(第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
感想
辺属性を書いたはいいけど定数倍が微妙すぎて扱いに困る ウケ
