NJPC2017 H - 白黒ツリー
想定解よりは複雑だけど、HL分解の方が応用が効くので書いておきます。
解法
深さが奇数の頂点の色を反転して考えれば、u-vパス上の頂点の色がすべて同じかどうかを判定する問題となる。
実装する処理は
- u の部分木に含まれる頂点の色を反転
- u-v パス上の値の総和
である。部分木クエリとパスクエリを同時にできるのか疑問に思うかもしれないが、HL分解の列はオイラーツアーの列でもあるので問題なく処理できる。
segtree パートは遅延伝搬テクをやるだけなので簡単だろう。
