1/21 日記
ううううう 今日も結局ぷらにゃ～と言ってしまった
やっぱりぷらにゃはかわいいね
まあ精進も出来てるからいいとしよう
のこのこに教えてもらったやつ。
とにかくクエリ数が多いから、まとめて処理したい。
まとめて処理するときは要素をソートすると上手くいくことが多いような気もする（？）
すると辺を番号が小さい順に見ていき、辺が結ぶ2頂点をマージしていくとうまい具合に訪れる頂点数zについても評価ができることが分かる。
ここまでくれば後は並列二分探索で解ける。
ぷらにゃがオイラーツアーをやっていてかわいかったので自分も履修した。
この問題では辺を訪れた順に配列recに入れていき、そのときの深さも記録しておくといい。クエリで与えられた2頂点a, bについて、その頂点の上にある辺の番号i, jを求め、区間[i, j]の深さの最小値mをセグ木で求める。
a, bの深さをそれぞれda, dbとすれば、
ans=da+db-2*m+1
で閉路の長さを求めることが出来る。
明日はこれ↓も読む
2種類のEuler Tourについて - beet's soil (hatenablog.com)
今日は眠いからそろそろ寝かなあ
