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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

NJPC2017 H - 白黒ツリー

HL分解 遅延セグメント木 Euler Tour

想定解よりは複雑だけど、HL分解の方が応用が効くので書いておきます。

H: 白黒ツリー - NJPC2017 | AtCoder

解法

深さが奇数の頂点の色を反転して考えれば、u-vパス上の頂点の色がすべて同じかどうかを判定する問題となる。

実装する処理は

  • u の部分木に含まれる頂点の色を反転
  • u-v パス上の値の総和

である。部分木クエリとパスクエリを同時にできるのか疑問に思うかもしれないが、HL分解の列はオイラーツアーの列でもあるので問題なく処理できる。

segtree パートは遅延伝搬テクをやるだけなので簡単だろう。