Query on a tree again! (SPOJ 2798)

SPOJ Online Judge

http://www.spoj.pl/problems/QTREE3/

問題

頂点数nのツリーが与えられる。以下の2つのクエリを捌け。

  • 頂点iの色を反転させる。(初期状態は白)
  • 頂点1からvまでで黒い頂点で頂点1に最も近いものを答えよ。無い場合は-1。

n<=100000
クエリの数<=400000

解法

ツリーのdfs順序(戻りも考慮)を使ったFenwickTreeで色の管理をする。黒い場合は行きの所で1を立て、戻りで-1してキャンセルさせる。これで一つ目のクエリはO(logn)で処理可能。
二つ目のクエリのために前計算で頂点iから2^n戻った場所を記憶しておく。あとは2分探索を使って黒い頂点が最初に出てきた場所を探せば良い。計算時間はO(log^2n)になる。
全体でO(q\log^2n)。TLEが厳しいので頑張ること。