Codeforces Round #200 (Div. 1) D. Water Tree

問題ページ
Problem - D - Codeforces

概要

頂点1が根のn頂点の木が与えられる。q個のクエリを処理する。
クエリ1 頂点vとvの子孫の頂点の値を1にする
クエリ2 頂点vとvの先祖の頂点の値を0にする
クエリ3 頂点vの値を出力する

解法

部分木に関するクエリなのでオイラーツアーをする。クエリ1,2について管理するセグメントツリーをそれぞれ用意する。セグメントツリーには、そのクエリを行った最後のクエリ番号を記録し、クエリ番号が大きい方の処理が後に行われたとして結果を出力する。
クエリ1の処理には区間更新・区間最大を求められる遅延セグメントツリーをつかう。クエリ2の処理には点更新・区間最大を求められるセグメントツリーを行う。クエリ2の処理がその頂点に対して行われるのはその部分木の頂点に行われたときのため、頂点の部分木の区間のうち最大のクエリ番号を求めればよい。
cin/coutだとTLEするので注意