読者です 読者をやめる 読者になる 読者になる

AOJ 2270 「The L-th Number」

AOJ2270を解きました。
LCAを普段と違う書き方で求めたり、題意を把握し間違えていたり(問題文が悪かったようです)で、N日かかってしまいました・・・
シンプルながらもぱない問題で好きです! iwiさんぱないっす!

問題概要

木の頂点に数字がひとつずつ書かれている。(他の頂点と重複する数字が書かれていることもある)
ある頂点からある頂点までのパス上にある頂点に書かれている数字を列挙し、前からL番目に来る数字を答えよ。
頂点数・クエリ数 <= 100,000

解法

UTPCのスライド
に書かれている通り、永続データ構造というものを使います。
普通の木構造のリンクを張り替えたりすると永続化できます。




なんか自分のはちょっと遅いけど、他の人より短いぜイエイ。
デバッグが大変で、紙に100頂点の木を書いたりしていました...疲れたw