Educational Codeforces Round 6 E. New Year Tree

木が与えられ、各頂点は色 c_i で塗られている。以下の 2 種類のクエリを処理する。

各頂点に pre-order で番号をつける。このようにすると部分木と区間を対応付けられる。

頂点 1 の部分木を色 c で塗りつぶすことは、区間 [1,6] を c で塗りつぶすことに対応する。

これで区間の問題に変わった。やりたいことは

の 2 つである。色の種類数が厄介に見えるが、今回は 60 種類しか色がないため色の集合をビットで表して OR すれば求まる。

区間塗りつぶしと区間 OR はどちらも遅延セグ木で対応可能。

Educational の E は毎回苦戦してたけど今回は解けた。