競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2170 Marked Ancestor

問題文

Marked Ancestor | Aizu Online Judge
日本語訳は他に書いてる人が沢山いるのでそちらをご参照ください

解法

便宜上,祖先を取得するクエリをQ,頂点をマークするクエリをMと略します.

頂点vに対するクエリQが飛んできたとき,何を求められればいいかを考えると,頂点vのマークされている祖先のうち,最も木の深さが大きいものを求められればOKです.
で,これを効率よく求める方法を考えます.
各頂点vにおいて,祖先のうち最も深い頂点の(depth,index)を値として持ちます.
すると,これらをdepthが大きくなる方向へ更新させていいことになります.
具体的には,頂点sに対するクエリMが飛んできたとき,sの子孫全ての要素に対して(depth(s),s)を与えていき,大きくなるならば更新する,みたいにします.
この操作は愚直にやるとO(N)になってしまうのですが,ここでオイラーツアーというテクニックを使います.
オイラーツアーを行うとO(N)で木を1次元の情報に変換でき,区間として扱うことができるようになります.
更に,ある頂点の子孫が含まれる範囲が一つの区間になって両端がO(1)で取得できるようになります.
これで,クエリMが飛んできたときに一つの区間に対してmaxの処理を行えばいいことになるので,segment treeを使えば解けます.
セグ木の実装は遅延を使うか蟻本の区間addを書き換えれば割と簡単にできると思います.
私は遅延評価を使いました.


この問題の想定解法はクエリを逆読みしてunion-findらしいです.

おまけ