AOJ 2170 Marked Ancestor
問題
Marked Ancestor | Aizu Online Judge
木に対してノードをマークするというクエリと、あるノードに対してマークされた最も近い祖先を答えるというクエリに答えよ。
解法
ノードをマークするというクエリは子全体に対するmax更新クエリとみなせ、最も近い祖先を答えるクエリは子に記録されたmaxを答えるクエリとみなせる。
よってEuler Tour Technique + 遅延評価セグメント木 で殴る👊👊👊
$ O(n log{n}) $