オイラーツアー
参考
概要
木をDFS順に探索して、
通った辺を記録するstep
辺$ i を通って進むときは$ i を、戻るときは$ -i を記録するといいかも
各頂点について、通過したタイミングを記録する
到達したとき・戻って行ったときの値をそれぞれin, out
あとはstep（や、stepから必要な情報を持ってきたもの）をセグ木なりに乗せて、in, out等で調べる区間を定める
何が嬉しい？
木に対するクエリを数列に対するクエリで処理できる
セグ木を使って高速に計算や更新ができる
遅延セグ木もあるぞ！
できること
※ 区間の端の処理は臨機応変に
キホン
頂点$ i の部分木に対するアレコレ
区間[in[i], out[i]]について調べる
根から頂点$ i までのパスに対するアレコレ
区間[0, in[i]]について調べる
頂点$ i, j のLCA(最小共通祖先)
区間[in[i], in[j]]について、最も根に近い頂点を調べる
頂点$ j が頂点$ i の部分木に含まれるか判定
in[i] < in[j] < out[i]？
応用
頂点$ i, j 間のパスに対するアレコレ
頂点$ k := 頂点$ i, j のLCA として、
根から頂点$ i, j, k それぞれのパスに対するアレコレを求めて、
$ i + j - 2k + 頂点$ k する
セグ木の作り方次第で色々できそう！（雑）