永続データ構造とやらが使いたくなったので解いた.でも,正直それ以外の部分で時間を食いまくった.
概要
各ノードに値が与えられている木が与えられる.
2つのノード間の初等的な経路の中でL番目に小さい数を出力するクエリにいっぱい答える.
解法
iwi先生のわかりやすい解説スライド(PDF)があるのでそっちを参照.
じゃあ,この記事書かなくてもいいじゃんと思うかもしれない.でも,解説スライドじゃ何も触れていないけど,実質LCAも解かないといけない.
あと,iwi先生の解説スライドに間違いがあって,4ページ目の"(スライドの頂点1から上)"の前にある+は-の間違いだと思う.
それだけ.