The L-th Number (AOJ 2270)

永続データ構造とやらが使いたくなったので解いた.でも,正直それ以外の部分で時間を食いまくった.

概要

各ノードに値が与えられている木が与えられる.
2つのノード間の初等的な経路の中でL番目に小さい数を出力するクエリにいっぱい答える.

解法

iwi先生のわかりやすい解説スライド(PDF)があるのでそっちを参照.

じゃあ,この記事書かなくてもいいじゃんと思うかもしれない.でも,解説スライドじゃ何も触れていないけど,実質LCAも解かないといけない.
あと,iwi先生の解説スライドに間違いがあって,4ページ目の"(スライドの頂点1から上)"の前にある+は-の間違いだと思う.

それだけ.