問題概要
頂点の木があり、頂点
は色
で塗られている。
以下のようなクエリが回にわたって与えられる。順に処理せよ。
- 頂点
の色を
に変更し、頂点
制約
解説
まず木を頂点を根とした根付き木として見ます。
次に各頂点について、「現在の色」、「親の頂点番号」、「親の色」、「直接つながっている頂点の｛色:個数｝の連想配列」を用意します。このとき、連想配列のサイズが答えるべき色の種類数です。
更新処理をする際、隣接する頂点をすべて見てしまうとTLEになってしまいます。そのため、親に対してのみ更新を行うことにします。
各頂点について、子の頂点の色が更新された場合はその時に更新されるため問題ないです。親の頂点が更新された場合は、自分の知っている親の色と実際の親の色が異なる場合連想配列の値を更新します。
このように更新処理を行うことでクエリ当たりで処理を行うことができます。
よってこの問題はで解くことができました。
